#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct edge{ int v1, v2, cost; };
edge E[400005];
int M[200005],P[200005];
int n,m,i,k;
long suma;
int cmp(edge a, edge b)
{
    if(a.cost<b.cost)
        return 1;
    else
        return 0;
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>E[i].v1>>E[i].v2>>E[i].cost;
    }
    M[1]=1;
    for(i=2;i<=n;i++)
        M[i]=2;
    sort(E+1,E+m+1,cmp);
    for(k=1;k<n;k++)
    {
        for(i=1;i<=m;i++)
        if(M[E[i].v1]!=M[E[i].v2])
            break;
        suma=suma+E[i].cost;
        if(M[E[i].v1]==1)
            P[E[i].v2]=E[i].v1;
        else
            P[E[i].v1]=E[i].v2;
        M[E[i].v1]=M[E[i].v2]=1;
    }
    g<<suma<<'\n';
    g<<n-1<<'\n';
    for(i=2;i<=n;i++)
        g<<i<<' '<<P[i]<<'\n';
    return 0;
}