#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct MUCHIE{
    int x, y, c;
}M[400001];
int C[200001]; // culoarea
bool cmp(MUCHIE a, MUCHIE b){
    return a.c < b.c;
}

int stramos(int x){
    if(C[x] == x)
        return x;
    C[x] = stramos(C[x]);
    return C[x];
}

int main()
{
    int n, m, i, k, ct;
    f >> n >> m;
    for(i = 1; i <= m; i++){
        f >> M[i].x >> M[i].y >> M[i].c;
    }
    sort(M+1,M+m+1,cmp);
    for(i = 1; i <= n; i++)
        C[i] = i;
    i = 1;//parcurge muchiile
    ct = 0; //cost total
    for(k = 1; k <= n-1;k++){
        while(stramos(M[i].x) == stramos(M[i].y))
            i++;
        C[stramos(M[i].x)] = C[stramos(M[i].y)];
        M[k] = M[i];
        ct += M[i].c;
    }
    g << ct << "\n";
    g << n-1 << "\n";
    for(i = 1; i <= n-1;i++){
        g << M[i].x << " " << M[i].y;
        g << '\n';
    }
    return 0;
}