#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <limits.h>
#include <stdio.h>
#include <string.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
priority_queue < pair <int, int> > L[200001];
int Tata[200001], Viz[200001],S[200001];
priority_queue <pair <int, int> > Q;
int n, m,costot;
void Citire()
{ int i, x,y,c;
    f>>n>>m;
    for(i=1;i<=m;i++)
    { f>>x>>y>>c;
        L[x].push(make_pair(-c,y));
        L[y].push(make_pair(-c,x));
    }
}
void Prim(int Start)
{int k,j,c,i,val,nod;
for(i=1;i<=n;i++)
    S[i]=INT_MAX;
S[Start]=0;
Q.push(make_pair(0, Start));
 while(!Q.empty())
 { j=Q.top().second;
   Viz[j]=1;
   Q.pop();
    val=L[j].top().first; nod=L[j][i].top().second;
     if(val<S[nod]&&Viz[nod]==0)
    { S[nod]=val;
       Q.push(make_pair(-val,nod));
       Tata[nod]=j;
    }

 }
}
int main()
{ int i;
Citire();
Prim(1);
for(i=1;i<=n;i++)
 costot=costot+S[i];
g<<costot<<endl;
g<<n-1<<endl;
 for(i=2;i<=n;i++)
    g<<Tata[i]<<" "<<i<<endl;
f.close();
g.close();
    return 0;
}