#include <fstream>
#include <algorithm>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,i,j,k,nr=0,l[1001],ct=0,p,q,a[1001];
struct stec
{
    int x,y,c;
} v[1001];
int compare(stec a,stec b)
{
    if(a.c>b.c)return 0;
    else return 1;
}
int main()
{
    f>>n>>m;
    for(i=1; i<=m; i++)
    {
        f>>v[i].x>>v[i].y>>v[i].c;
    }
    sort(v+1,v+m+1,compare);
    for(i=1; i<=n; i++)
    {
        l[i]=i;
    }
    nr=0;
    k=1;
    while(nr<n-1)
    {
        {
            if(l[v[k].x]!=l[v[k].y])
            {
                ct=ct+v[k].c;
                p=l[v[k].x];
                q=l[v[k].y];
                for(j=1; j<=n; j++)
                {
                    if(l[j]==q)
                    {
                        l[j]=p;
                    }
                }
                nr++;
                a[nr]=k;
            }
        }
        k++;
    }
    g<<ct<<'\n'<<n-1<<'\n';
    for(i=1;i<=n-1;i++)
    {
    g<<v[a[i]].y<<" "<<v[a[i]].x<<'\n';
    }
    return 0;
}