#include <fstream>
#define cost first
#define st second.first
#define dr second.second
#include <algorithm>
using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");
int n,m,x,i,rx,ry,y,op,T[100001];
pair<int, pair<int, int> > L[400010];


int rad (int x){
    while(T[x]>0)
        x=T[x];
    return x;
}


int main(){
    fin>>n>>m;
    for(i=1;i<=n;i++)
        T[i]=-1;
    for(i=1;i<=m;i++){
        fin>>L[i].cost>>L[i].st>>L[i].dr;
    }

    sort(L+1, L+m+1);

    for(i=1;i<=m;i++){
        x = L[i].st;
        y = L[i].dr;
        rx=rad(x);
        ry=rad(y);
        if(rx!=ry){
            sol += L[i].cost;
            S[++k] = x;
            D[k] = y;

            if(T[rx]<T[ry]){
                T[rx]+=T[ry];
                T[ry]=rx;
            }
            else{
                T[ry]+=T[rx];
                T[rx]=ry;
            }
        }
    }
    fout<<sol<<"\n"<<n-1<<"\n";
    for (i=1;i<=k;i++)
        fout<<S[i]<<" "<<D[i]<<"\n";
}