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

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

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

void upheap(int i)
{
    while(i>1 && h[i] < h[i/2])
    {
        swap(h[i], h[i/2]);
        i = i/2;
    }
}

void add_heap(muchii val)
{
    k++;
    h[k]=val;
    upheap(k);
}

int main()
{
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>u[i].x>>u[i].y>>u[i].c;
        add_heap(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=h[1];
    h[1]=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;
}