#include<fstream>
#include<algorithm>
#define x first
#define y second.first
#define z second.second
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,k,c,a,b;
int t[200010];
pair <int,pair<int,int> > p[400010];
pair <int,int> S[400010];

int rad(int x){

    while(t[x]>0)
        x=t[x];
    return x;
}


int main(){
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        fin>>p[i].y>>p[i].z>>p[i].x;
    }
    sort(p+1,p+m+1);
    for(int i=1;i<=n;i++)
        t[i]=-1;
    t[p[1].z]=p[1].y;
    c+=p[1].x;
    S[++k].x=p[1].y;
    S[k].second=p[1].z;
    for(int i=2;i<=m;i++){
        a=rad(p[i].y);
        b=rad(p[i].z);
        if(a!=b){
            if(t[a]<t[b]){
                t[a]+=t[b];
                t[b]=a;
            }
            else{
                t[b]+=t[a];
                t[a]=b;
            }
            c+=p[i].first;
            S[++k].x=p[i].y;
            S[k].second=p[i].z;
        }
    }
    fout<<c<<"\n"<<k<<"\n";
    for(int i=1;i<=k;i++)
        fout<<S[i].x<<" "<<S[i].second<<"\n";
    return 0;
}