#include<fstream>
#include<algorithm>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
#define N 200001
struct H {
    int x,y,c;
}v[2*N];
int p[N],t[N];
bool A(H a,H b)
{
    return a.c<b.c;
}
int main()
{
    int m,n,r=0,s=0;
    cin>>n>>m;
    for(int i=0;i<m;cin>>v[i].x>>v[i].y>>v[i].c,++i);
    sort(v,v+m,A);
    for(int i=0;i<m;++i) {
        int j=v[i].x,k=v[i].y;
        for(;t[j];j=t[j]);
        for(;t[k];k=t[k]);
        if(j!=k)
            p[r++]=i,s+=v[i].c,t[j]=k;
    }
    cout<<s<<'\n'<<r<<'\n';
    for(int i=0;i<r;cout<<v[p[i]].x<<' '<<v[p[i]].y<<'\n',++i);
    return 0;
}