#include <fstream>
#include <vector>
#include<algorithm>
#define pp pair<int,int>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
vector<pp> q;
int n,m,cost,t[200001],h[200001],a,b,x[200001],y[200001],c[200001],o[200001];
int comp(int a,int b){
    return c[a]<c[b];
}
int father(int n){
    while(t[n]>0)
        n=t[n];
    return n;
}
void cit(){
    int i;
    fin>>n>>m;
    for(i=1;i<=m;i++)
        fin>>x[i]>>y[i]>>c[i],o[i]=i;
}
void kruskal(){
    int i,j=0;
    for(i=1;i<n;i++){
        do{
            j++;
            a=father(x[o[j]]);
            b=father(y[o[j]]);
        }while(a==b);
        q.push_back(make_pair(x[o[j]],y[o[j]]));
        cost+=c[o[j]];
        if(h[a]>h[b])
            t[b]=a;
        else
        if(h[a]<h[b])
            t[a]=b;
        else{
            h[a]++;
            t[b]=a;
        }
    }
}
int main(){
    cit();
    sort(o+1,o+1+m,comp);
    kruskal();
    fout<<cost<<'\n'<<n-1<<'\n';
    for(int i=0;i<q.size();i++)
        fout<<q[i].first<<" "<<q[i].second<<'\n';
    fout.close();
    return 0;
}