#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
int n,m,i,sol,Min,root[200005],siz[200005],poz[400005];
struct muchie{
int x,y,cost;
}v[400005];
bool cmp(muchie a,muchie b){
return a.cost<b.cost;
}
int getroot(int x){
    while(root[x]!=x)
        x=root[x];
    return x;
}
int main()
{
    cin>>n>>m;
    for(i=1;i<=m;i++)
        cin>>v[i].x>>v[i].y>>v[i].cost;
    for(i=1;i<=n;i++)
        root[i]=i,siz[i]=1;
    sort(v+1,v+m+1,cmp);
    for(i=1;i<=m;i++){
        int rx=getroot(v[i].x),ry=getroot(v[i].y);
        if(rx!=ry){
            poz[++sol]=i;
            Min+=v[i].cost;
            if(siz[rx]>siz[ry])
                swap(rx,ry);
            root[ry]=rx;
            siz[rx]+=siz[ry];
        }
    }
    cout<<Min<<'\n'<<sol<<'\n';
    for(i=1;i<=sol;i++)
        cout<<v[i].x<<" "<<v[i].y<<'\n';
    return 0;
}