#include <bits/stdc++.h>
#define N 10000
#define oo 0x3f3f3f3f
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m, C, x, y;
int a[N][N]; /// matricea costurilor
int tata[10000]; /// vectorul de tati
bool viz[10000];
void Citire()
{
    fin>>n>>m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            if(i!=j) a[i][j] =a[j][i]=oo;

    for(int i=1; i<=m; i++)
    {
        fin>>x>>y>>C;
        a[x][y]=a[y][x]=C;
    }

}
void Prim(int nd)
{
    int i, j, p, vmin, k;
    viz[nd]=1; ///marcam nodul de start vizitat
    for(i=1; i<=n; i++)
        tata[i]=nd;
    tata[nd]=0; /// initializam vectorul de tati

    for(k=1; k<=n-1; k++)
    {
        vmin=oo; ///minimul este initializat cu infinit
        p=0;
        for(i=1; i<=n; i++)
        {
            if(!viz[i] && a[i][tata[i]]<vmin) ///caut un nod neviz si il comparam cu minimul
            {
                vmin=a[i][tata[i]];
                p=i;  ///retinem nodul in variabila p
            }
        }
        viz[p]=1; ///il marcam vizitat la sfarsit
        for(i=1; i<=n; i++)
            if(!viz[i] && a[i][tata[i]] > a[i][p]) tata[i] = p;
    }
    int cost=0;
    for(int i = 1; i <= n; i++)
        cost+=a[i][tata[i]];
    fout<<cost<<"\n"<<n-1<<'\n';
    for(int i=2; i<=n; i++)
        fout<<i<<' '<<tata[i]<<'\n';
}

int main()
{
    Citire();
    Prim(1);
    return 0;
}