#include <bits/stdc++.h>
#define K 200002
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct muchie
{
    int a,b,d;
}mc[K];
bool comp(muchie a,muchie b){return a.d<b.d;};
int cc[K],v[K];
int main()
{
    int n,m,i,j,in,fin,p,sum=0;
    f>>n>>m;
    for(i=1;i<=m;i++)
        f>>mc[i].a>>mc[i].b>>mc[i].d;
    sort(mc+1,mc+m+1,comp);
    for(i=1;i<=n;i++)
        cc[i]=i;
    for(i=1,j=0;j< n-1 ;i++)///parcurgem v de muchii
        if(cc[mc[i].a]!=cc[mc[i].b])///NU apartin acc componenta conexa
        {
            v[++j]=i;sum+=mc[i].d;
            in=min(cc[mc[i].a],cc[mc[i].b]);
            fin=max(cc[mc[i].a],cc[mc[i].b]);
            for(p=1;p<=n;p++)
                if(cc[p]==in)
                    cc[p]=fin;
        }
    g<<sum<<endl<<n-1<<endl;
    for(i=1;i<=n-1;i++)
        g<<mc[v[i]].a<<" "<<mc[v[i]].b<<endl;
}