#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
#define nrm 200005
struct muchie
{
    int i,j,cost;
};
muchie x[nrm];
int n,m,t[101];
pair<int,int>v[nrm];
int comp(muchie x,muchie y)
{
    return x.cost<y.cost;
}
int main ()
{
    fin>>n>>m;
    for(int i=0;i<m;i++)
    {
        fin>>x[i].i>>x[i].j>>x[i].cost;
    }
    sort(x+1,x+m+1,comp);
    for(int i=1;i<=n;i++)
    {
        t[i]=i;
    }
    int s=0,cnt=0;
    for(int i=0;i<m && cnt<n;i++)
    {
        if(t[x[i].i]!= t[x[i].j])
        {
            s=s+x[i].cost;
            int ai=t[x[i].i];
            int aj=t[x[i].j];
            for(int j=1;j<=n;++j)
            {
                if(t[j]==aj)
                {
                    t[j]=ai;
                }
            }
            cnt++;
            v[cnt].first=x[i].i;
            v[cnt].second=x[i].j;
        }
    }
    fout<<s<<'\n'<<n-1<<'\n';
    for(int i=1;i<=n-1;i++)
    {
        fout<<v[i].first<<" "<<v[i].second;
        fout<<'\n';
    }
    return 0;
}