#include <algorithm>
#include <iostream>
#include <fstream>
#define NMax 400005
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
 
struct muchie{
    int x,y,c;
}G[NMax];
 
int n,m,Rx,Ry,cost,muchii;
int r[NMax],sol[NMax],rang[NMax];
 
int conditie(muchie x,muchie y){
    return (x.c < y.c);
}
int root(int x){
    while(r[x])
        x = r[x];
    return x;
}
void algoritm(){
    for(int i = 1; i <= m; ++i){
        rang[i] = 1;
    }
    for(int i = 1; i <= m && muchii < n - 1; ++i){
        Rx = root(G[i].x);
        Ry = root(G[i].y);
 
        if(Rx != Ry){
            sol[++muchii] = i;
            cost += G[i].c;
 
            if(rang[Rx] > rang[Ry]){
                rang[Rx] += rang[Ry];
                r[Ry] = Rx;
            }else{
                rang[Ry] += rang[Rx];
                r[Rx] = Ry;
            }
        }
    }
}
int main()
{
    fin>>n>>m;
    for(int i = 1; i <= m; ++i){
        fin>>G[i].x>>G[i].y>>G[i].c;
    }
    sort(G + 1, G + 1 + m,conditie);
    algoritm();
    fout<< cost <<"\n" << n - 1 <<"\n";
    for(int i = 1; i < n; ++i){
        fout<< G[sol[i]].x <<" " << G[sol[i]].y <<"\n";
    }
    return 0;
}