#include <fstream>
#include <algorithm>
#define DIM 200002
using namespace std;

int n,m,i,j,k,cost,x,y,rx,ry,t[DIM];
pair < pair<int,int>,int > v[2*DIM];
pair <int, int> sol[2*DIM];
int rad (int x){
    while (t[x] > 0)
        x = t[x];
    return x;
}
int main (){
    ifstream fin ("apm.in");
    ofstream fout ("apm.out");

    fin>>n>>m;
    for (i=1;i<=n;i++)
        t[i] = -1;
    for (i=1;i<=m;i++)
        fin>>v[i].first.second>>v[i].second >>v[i].first.first;
    sort (v+1,v+m+1);
    for (i=1;i<=m;i++){
        //x = v[i].first.second;
        //y = v[i].second;

        rx = rad(v[i].first.second);
        ry = rad(v[i].second);
        if (rx != ry){
            cost += v[i].first.first;
            k++;
            sol[k].first = v[i].first.second;
            sol[k].second = v[i].second;
            if (t[rx] < t[ry]){
                t[rx] += t[ry];
                t[ry] = rx;
            }
            else{
                t[ry] += t[rx];
                t[rx] = ry;
            }
        }
    }
    fout<<cost<<"\n"<<k<<"\n";
    for (i=1;i<=k;i++)
        fout<<sol[i].second<<" "<<sol[i].first<<"\n";

    return 0;
}