#include<fstream>
#include<iostream>
#include<vector>
#include<algorithm>
#define maxn 200005
#define maxm 400005

using namespace std;

struct elem{
    int x, y, c;
    elem() {}
    elem(int a1, int b1, int c1){
        x = a1;
        y = b1;
        c = c1;
    }
};

elem mc[maxm], rez[maxn];
int t[maxn], rg[maxm]; 
ofstream g("apm.out");

int cmp(elem a, elem b){
    return a.c < b.c;    
}

int find(int x){
    int r = x, y;
    while (r != t[r])
        r = t[r];
    while (x != t[x]){
        y = t[x];
        t[x] = r;
        x = y;
    }
    return r;    
}

int main(){
    ifstream f("apm.in");
    
    int n, m, i, j, x, y, cost;
    elem muchie;
    f>>n>>m;
    for (i = 1; i <= m; i++){
        f>>x>>y>>cost;
        mc[i] = elem(x, y, cost);
    }
    
    sort(mc+1, mc+m+1, cmp);
    
    for (i = 1; i <= n; i++){
        t[i] = i;
        rg[i] = 0;
    }
     
    int im = 1;
    i = 0;
    int rx, ry;
    long long c = 0;
    while (i < n-1 && im <= m){
        muchie = mc[im];
        im++;
        rx = find(muchie.x);
        ry = find(muchie.y);
        if (rx != ry){
            if (rg[rx] > rg[ry])
                t[ry] = rx;
            else {
                t[rx] = ry;
                if (rg[ry] == rg[rx])
                    rg[ry]++;
            }
            i++;
            rez[i] = muchie;
            c = c+muchie.c;
        }
    }
    
    g<<c<<'\n'<<n-1<<'\n';
    for (i = 1; i <= n-1; i++)
        g<<rez[i].x<<" "<<rez[i].y<<'\n';
    
    return 0;
}