#include <bits/stdc++.h>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

struct cel{
    int x, y, c;
} aux;
vector<cel> v, ans;
int n, m, tot, dsu[200010];
bool cmp(cel a, cel b){
    return a.c < b.c;
}

int tata(int a){
    if(a == dsu[a])
        return a;
    return dsu[a] = tata(dsu[a]);
}

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; ++i){
        fin >> aux.x >> aux.y >> aux.c;
        v.push_back(aux);
    }
    sort(v.begin(), v.end(), cmp);
    for(int i = 1; i <= n; ++i) dsu[i] = i;

    for(auto& it : v){
        int tx = tata(it.x);
        int ty = tata(it.y);
        if(tx != ty){
            dsu[ty] = tx;
            tot += it.c;
            ans.push_back(it);
        }
    }

    fout << tot << '\n' << n - 1 << '\n';
    for(auto& it : ans){
        fout << it.x << ' ' << it.y << '\n';
    }
    return 0;
}