#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct muchie{int x,y,c;};
muchie e[1000];
bool comp (muchie a, muchie b){
    return a.c<b.c;
}
int z[100],n,m,i,j,x,y,ct,nr,u,v;
vector <pair < int ,int > > sol;
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%ld%ld",&n,&m);
    for(i=1; i<=m; i++)
        scanf("%ld%ld%ld",&e[i].x,&e[i].y,&e[i].c);
    sort(e+1,e+n+1,comp);
    for(i=1; i<=n; i++) z[i]=i;
    ct=0;
    nr=0;
    i=1;
    while(nr<n-1)
    {
        u=z[e[i].x];
        v=z[e[i].y];
        if(u!=v)
        {
            sol.push_back(make_pair(e[i].x, e[i].y));
            for(j=1; j<=n; j++)
                if(z[j]==v) z[j]=u;
            ct=ct+e[i].c;
            nr=nr+1;
        }
        i++;
    }
    printf("%ld\n%ld\n",ct,n-1);
    for(i=0; i<sol.size(); i++)
        printf("%ld %ld\n",sol[i].first,sol[i].second);
    return 0;
}