#include <bits/stdc++.h>

using namespace std;

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

struct muchie
{
    int x,y,cost;
}a[10001];

struct
{
    int x,y;
}afis[101];

int t[101],n,m,s,k;

bool cmp(muchie i,muchie j)
{
    return(i.cost<j.cost);
}

int main()
{
    in>>n>>m;
    for(int i=1;i<=n;i++)
        t[i]=i;
    for(int i=1;i<=m;i++)
        in>>a[i].x>>a[i].y>>a[i].cost;
    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        if(t[a[i].x]!=t[a[i].y])
        {
            s+=a[i].cost;
            afis[++k].x=a[i].x;
            afis[k].y=a[i].y;
            int ax=t[a[i].x],ay=t[a[i].y];
            for(int j=1;j<=n;j++)
                if(t[j]==ay)
                    t[j]=ax;
        }
    }
    out<<s<<'\n'<<n-1<<'\n';
    for(int i=1;i<n;i++)
        out<<afis[i].x<<' '<<afis[i].y<<'\n';
    return 0;
}