#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

const int NMAX=100001;
vector <int> G[NMAX];

int N,M,a[100][100],viz[100],tata[100],c[100],m;

void citire()
{
    int X,Y,C;
    fin>>N>>M;
    for(int i=1;i<=M;i++)
    {
        fin>>X>>Y>>C;
        a[X][Y]=C;
        a[Y][X]=C;
    }
}

//varianta bruta
void apm(int start)
{
    int x,y;
    viz[start]=1;
    for(int k=1;k<=N-1;k++)
    {
        //cout o muchie care are extremitatea in arbore si cealalta in afara arborelui
       int minn=INT_MAX;
        for(int i=1;i<=N;i++)
            for(int j=1;j<=N;j++)
        {
            if(viz[i]==1 && viz[j]==0 && a[i][j]<minn && a[i][j]!=0){
                    minn=a[i][j];
                    x=i;
                    y=j;
            }
        }
        viz[y]=1;
        tata[y]=x;
        c[y]=minn;
        m++;
    }
}

int main()
{
    citire();
    apm(1);
    int s=0;
    for(int i=1;i<=N;i++)
        s=s+c[i];
    fout<<s<<endl<<m<<endl;
    for(int i=2;i<=N;i++)
        fout<<tata[i]<<" "<<i<<endl;
}