#include<bits/stdc++.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie{
    int x,y,c;
}v[400001],sol[400001];
int N,M,T[200001],P[200001];
bool cmp(muchie X,muchie Y){
    return X.c<Y.c;
}
int Root(int x){
    while(x!=T[x])x=T[x];
    return x;
}
void Unifica(int x,int y){
    if(P[x]>P[y])T[y]=x;
    else if(P[x]<P[y])T[x]=y;
    else ++P[x],T[y]=x;
}
int main()
{
    f>>N>>M;
    for(int i=1;i<=M;++i){
        f>>v[i].x>>v[i].y>>v[i].c;
        if(i<=N)T[i]=i;
    }
    sort(v+1,v+M+1,cmp);
    int k=0,ct=0,i=1;
    while(k<N-1){
        int rx=Root(v[i].x);
        int ry=Root(v[i].y);
        if(rx!=ry){
            ct+=v[i].c,++k;
            sol[k].x=v[i].x,sol[k].y=v[i].y;
            Unifica(rx,ry);
        }
        ++i;
    }
    g<<ct<<'\n'<<k<<'\n';
    for(int i=1;i<=k;++i)g<<sol[i].x<<' '<<sol[i].y<<'\n';
    return 0;
}