#include <iostream>
#include <fstream>
using namespace std;
#define Inf 10000
int n, i, VfMin, nrv;
int G[10001][10001], p[200001], Z[200001], cmin[200001], CostMin, m;

void Initializare()
{
    int i, j, c, x, y;
    ifstream f("apm.in");
    f >> n >> m;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            if(i==j)
                G[i][j]=0;
            else
                G[i][j]=Inf;
        }
    }
    for(i=1; i<=m; i++)
    {
        f >> x >> y >> c;
        G[x][y]=c;
        G[y][x]=c;
    }
    for(i=1; i<=n; i++)
    {
        cmin[i]=G[1][i];
        p[i]=1; Z[i]=1;
    }
    Z[1]=0; p[1]=0; nrv=n-1;
}

void afisare()
{
    ofstream g("apm.out");
    int i;
    long long cost=0;
    for(i=1; i<=n; i++)
    {
        cost=cost+G[i][p[i]];
    }
    g<<cost<<"\n";
    g<<n-1<<"\n";
    for(i=1; i<=n; i++)
    {
        if(i!=1)
            g<<p[i]<<" "<<i<<"\n";
    }
}

int main()
{
    Initializare();
    while(nrv)
    {
        CostMin=Inf;
        for(i=1; i<=n; i++)
        {
            if(Z[i] && CostMin>cmin[i])
            {
                CostMin=cmin[i];
                VfMin=i;
            }
        }
        Z[VfMin]=0;
        nrv--;
        for(i=1; i<=n; i++)
        {
            if(Z[i] && G[i][VfMin]<cmin[i])
            {
                p[i]=VfMin;
                cmin[i]=G[i][VfMin];
            }
        }
    }
    afisare();
    return 0;
}