#include <bits/stdc++.h>

using namespace std;
ifstream in("kruskal.in");
ofstream out("kruscal.out");
int n,m,t[101];
struct muchie
{
    int i,j,c;
}x[1001],aux;
struct afis
{
    int x,y;
}a[101];
bool cmp(muchie i, muchie j)
{
    return(i.c<j.c);
}
int main()
{
    int i,j,s=0,k=0;
    in>>n>>m;
    for(i=1;i<=m;i++)
        in>>x[i].i>>x[i].j>>x[i].c;
   sort(x+1,x+m+1,cmp);
   for(i=1;i<=n;i++)
        t[i]=i;
   for(i=1;i<=m;i++)
   {
       if(t[x[i].i] != t[x[i].j])
       {
           s+=x[i].c;
           a[++k].x=x[i].i;
           a[k].y=x[i].j;
           int ai = t[x[i].i],aj = t[x[i].j];
            for(int j =1 ; j <= n ;j++)
                if(t[j] == aj)
                    t[j] = ai;
       }
   }
   out<<s<<'\n'<<n-1<<'\n';
   for(i=1;i<n;i++)
    out<<a[i].y<<' '<<a[i].x<<'\n';
    return 0;
}