#include <bits/stdc++.h>

#define f first
#define s second

using namespace std;

ifstream F("apm.in");
ofstream G("apm.out");

int n, m, x, y, c, ans, k, t[200005], fx, fy;
pair<int, int> sol[400005];
pair<int, pair<int, int> > v[200005];

int f(int x){
    if(t[x] == x) return x;
    return t[x]=f(t[x]);
}

int main()
{
    F >> n >> m;
    for(int i = 1; i <=m;++i){
        F >> x >> y >> c;
        v[i] = {c, {x, y}};
    }
    for(int i = 1; i <= n; ++ i) t[i] = i;
    sort(v+1, v+m+1);
    for(int i = 1; i <= m; ++ i){
        x = v[i].s.f;
        y = v[i].s.s;
        fx = f(x);
        fy = f(y);
        if(fx > fy) swap(fx, fy);
        if(fx==fy) continue;
        t[fy] = fx;
        ans+=v[i].f;
        sol[++k] = {x, y};
    }
    G << ans << '\n' << k << '\n';
    for(int i=1; i <= k; ++ i)G << sol[i].f << " " << sol[i].s << '\n';
    return 0;
}