#include <fstream>
#include <algorithm>

using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
int T[1+int(2e5)];
int x[1+int(4e5)],y[1+int(4e5)],c[1+int(4e5)],nr[1+int(4e5)];
bool cmp(int a,int b){
    return c[a]<c[b];
}
struct ab{
    int x,y;
}r[int(2e5)];
int sef(int x){
    if(x!=T[x])
        return sef(T[x]);
    else
        return x;
}
int main()
{
    int n,m,i,ct=0,k=0;
    cin>>n>>m;
    for(i=1;i<=m;i++){
        cin>>x[i]>>y[i]>>c[i];
        nr[i]=i;
    }
    for(i=1;i<=n;i++)
        T[i]=i;
    sort(nr+1,nr+m+1,cmp);
    for(i=1;i<=m;i++){
        if(sef(x[nr[i]])!=sef(y[nr[i]])){
            ct=ct+c[nr[i]];
            T[sef(y[nr[i]])]=sef(x[nr[i]]);
            r[++k]={x[nr[i]],y[nr[i]]};
        }
    }
    cout<<ct<<'\n'<<n-1<<'\n';
    for(i=1;i<=n-1;i++)
        cout<<r[i].x<<" "<<r[i].y<<'\n';
    return 0;
}