//#include <iostream>
#include <fstream>
using namespace std;
long long n,m,s,mn,arb[200005],i,p,arbc,k,a[400005],b[400005];

ifstream cin("apn.in");
ofstream cout("apm.out");

struct muchii
{
    int x,y,c;
} u[400005];

int main()
{
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>u[i].x>>u[i].y>>u[i].c;
    }
    for(i=1;i<=n;i++)
        arb[i]=i;
    mn=1001;
    for(i=1;i<=m;i++)
    {
        if(u[i].c<mn)
        {
            mn=u[i].c;
            p=i;
        }
    }
    s=u[p].c;
    u[p].c=1001;
    arb[u[p].x]=arb[u[p].y];
    arbc=arb[u[p].x];
    //cout<<arbc<<"* ";
   // cout<<s;
   // cout<<u[p].x<<" "<<u[p].y<<'\n';
    a[1]=u[p].x; b[1]=u[p].y;
    for(k=1;k<=n-2;k++)
    {
        mn=1001;
        for(i=1;i<=m;i++)
        {
            if(u[i].c<mn)
            {
                if(arb[u[i].x]==arbc || arb[u[i].y]==arbc)
                {
                    if(arb[u[i].x]!=arb[u[i].y])
                    {
                        mn=u[i].c;
                        p=i;
                    }
                }
            }
        }
        //cout<<u[p].x<<" "<<u[p].y<<'\n';
        a[k+1]=u[p].x; b[k+1]=u[p].y;
        s=s+u[p].c;
        u[p].c=1001;
        arb[u[p].y]=arbc;
        arb[u[p].x]=arb[u[p].y];

    }
    cout<<s<<'\n'<<n-1<<'\n';
    for(i=1;i<=n-1;i++)
        cout<<a[i]<<' '<<b[i]<<'\n';

    return 0;
}