#include <iostream>
#include <fstream>
using namespace std;
struct muchii{
int vf1,vf2;
};
ifstream fin("apm.in");
ofstream fout("apm.out");
int a[801][801],viz[1001];
void init(int viz[],int n)
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            a[i][j] = 0;
    for(int i=1;i<=n;i++)
            viz[i] = 0;
}

void PRIM(int viz[],int n,int vf,int &suma,muchii graf[],int &indice)
{

    indice = 0;
    suma = 0;
    int minim, vf2, vf3, ok2;
    vf2 = vf3 = 0;
    viz[vf] = 1;
    ok2 = 1;
    while(ok2)
    {
    ok2 = 0;
    for(int j=1;j<=n;j++)
        if(viz[j] == 0) ok2 = 1;
    minim = 1002;
    for(int j=1;j<=n;j++)
        {
        /// gaseste drumul de cost minim pt oricare dintre varfurile deja parcurse
        if(viz[j]==1)
            for(int i=1;i<=n;i++)
                /// gaseste drumul de cost minim catre un vefin
                if(a[i][j] != 0 && viz[i] == 0 && a[i][j] < minim) {minim = a[i][j];
                                                                    vf2 = i;
                                                                    vf3 = j;}
        }

    /// merge acolo daca a gasit unul
    if(ok2){
    suma += a[vf2][vf3];
    viz[vf2] = 1;
    indice++;
    graf[indice].vf1 = vf2;
    graf[indice].vf2 = vf3;
    //fout<<vf2<<" "<<vf3<<'\n';
            }
    }

}
int main()
{
    muchii graf[2000];

    int n,m,i,x,y,cost;
    fin>>n;
    fin>>m;
    init(viz,n);
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>cost;
        a[x][y] = a[y][x] = cost;
    }
    /// pleaca dintr un varf
    int suma;
    PRIM(viz,n,1,suma,graf,x);
    fout<<suma<<'\n'<<n-1<<'\n';
    for(i=1;i<=x;i++)
        fout<<graf[i].vf1<<" "<<graf[i].vf2<<'\n';







    return 0;
}