#include <bits/stdc++.h>

using namespace std;
ifstream f("apm.in");
ofstream h("apm.out");
int n,r=1,m,nrv,cost,muchii;
int g[20000][20000];
int cmin[200001];
bool Z[200001];
int p[200001];

void Initializare()
{
    f>>n>>m;
    int x,y,cost;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            if(i!=j) g[i][j] = INFINITY;
    while(f>>x>>y>>cost)
        g[x][y]=g[y][x] = cost;
    for(int i=1;i<=n;++i)
    {
        cmin[i] = g[r][i];
        p[i] = r;
    }
    Z[r] = true;
    p[r] = 0;
    nrv = n-1;
    f.close();
}

void Afisare()
{
    h<<cost<<'\n'<<muchii<<'\n';
    for(int i=1;i<=n;++i)
        if(i!=r)
            h<<p[i]<<" "<<i<<'\n';
}

int main()
{
    Initializare();
    while(nrv)
    {
        int CostMin = INFINITY,VfMin;
        for(int i=1;i<=n;++i)
            if(Z[i] == false && CostMin >cmin[i])
            {
                CostMin = cmin[i];
                VfMin = i;
            }

        Z[VfMin] = true;
        cost += CostMin;
        nrv--;
        ++muchii;

        for(int i=1;i<=n;++i)
            if(Z[i] == false && g[i][VfMin] < cmin[i])
            {
                p[i] = VfMin;
                cmin[i] = g[i][VfMin];
            }
    }
    Afisare();
    return 0;
}