#include <stdio.h>
#include <vector>
#define vecin first
#define cost second
#define pb push_back
#define mp make_pair
#define IN "apm.in"
#define OUT "apm.out"
#define NMAX 200005
#define INF 100000000
using namespace std;

int n,m;
int use[NMAX],cmin[NMAX],p[NMAX];
vector < pair<int,int> > nod[NMAX];

void citire();
void rezolvare();
void afisare();

int main()
{
    citire();
    rezolvare();
    afisare();

    return 0;
}

void citire()
{
    FILE * fin=fopen(IN,"r");

    int i,a,b,c;
    fscanf(fin,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(fin,"%d%d%d",&a,&b,&c);
        nod[a].pb(mp(b,c));
        nod[b].pb(mp(a,c));
    }

    fclose(fin);
}

void rezolvare()
{
    int i,k,z;
    for(i=2;i<=n;i++)
    {
        p[i]=1;
        cmin[i]=INF;
    }

    while(1)
    {
        int minim;
        minim=INF;
        for(i=1;i<=n;i++)
            if(minim>cmin[i] && use[i]==0)
            {
                minim=cmin[i];
                z=i;
            }
        if(minim==INF) break;

        use[z]=1;
        for(k=0;k<nod[z].size();k++)
        {
            if(cmin[nod[z][k].vecin]>nod[z][k].cost && use[nod[z][k].vecin]==0)
            {
                cmin[nod[z][k].vecin]=nod[z][k].cost;
                p[nod[z][k].vecin]=z;
            }
        }
    }
}

void afisare()
{
    FILE * fout=fopen(OUT,"w");

    int s=0,i,k;
    for(i=1;i<=n;i++)
        s=s+cmin[i];
    fprintf(fout,"%d\n%d\n",s,n-1);
    for(i=2;i<=n;i++)
        fprintf(fout,"%d %d\n",i,p[i]);

    fclose(fout);
}