//Kruskal O(n logn)
#include <bits/stdc++.h>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int t[200005];
int h[200005];
int findr(int x){
    int r = x;
    while(r != t[r]) r = t[r];
    return r;
}
void unire(int x, int y){
    int rx = findr(x);
    int ry = findr(y);
    if(h[rx] < h[ry]) t[x] = y;
    else{
        if(h[rx] > h[ry]) t[ry] = rx;
        else{
            t[rx] = ry;
            h[ry]++;
        }
    }
}
int n,m;
vector < pair <int, pair <int, int> > > e;
vector < pair <int, int> > vec;
int main()
{
    fin >> n >> m;
    for(int i = 1; i <= n; i++) t[i] = i;
    for(int i = 1; i <= m; i++){
        int u,v,c;
        fin >> u >> v >> c;
        e.push_back({c,{u,v}});
    }
    sort(e.begin(), e.end());
    int rez = 0;
    for(int i = 0; i < m; i++){
        pair <int, int> p = e[i].second;
        int u = p.first, v = p.second;
        if(findr(u) != findr(v)){
            unire(u,v);
            rez += e[i].first;
            vec.push_back({v,u});
        }
    }
    fout << rez << "\n" << n - 1 << "\n";
    for(auto x : vec) fout << x.first << " " << x.second << "\n";
    return 0;
}