//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];
    int y = x;
    t[x] = r;
    while(y != r){
        int d = t[y];
        t[y] = r;
        y = d;
    }
    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 < vector <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(auto v : e){
        if(findr(v[1]) != findr(v[2])){
            unire(v[1],v[2]);
            rez += v[0];
            vec.push_back({v[1], v[2]});
        }
    }
    fout << rez << "\n" << n - 1 << "\n";
    for(auto x : vec) fout << x.first << " " << x.second << "\n";
    return 0;
}