#include <iostream>
#include <fstream>
using namespace std;

int n, m;
int cost[1001][1001], viz[1001], distanta[1001], tata[1001];
const int MAXIM = 999999;

int main() {
    ifstream reader("apm.in");
    ofstream writer("apm.out");
    reader>>n>>m;

    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            cost[i][j]=MAXIM;
    for(int i=0; i<m; i++) {
        int x, y, c;
        reader>>x>>y>>c;
        cost[x][y]=c;
        cost[y][x]=c;
    }
    for(int i=1; i<=n; i++) {
        distanta[i]=MAXIM;
        tata[i]=0;
    }

    distanta[1]=0; 
    int total=0;

    for(int p=1; p<=n; p++) {
        int nod=0;
        int minim=MAXIM;
        for(int i=1; i<=n; i++)
            if((distanta[i] < minim) && !viz[i]) {
                minim=distanta[i];
                nod=i;
            }

        viz[nod]=1;
        total+=minim;

        for(int j=1; j<=n; j++)
            if((cost[nod][j] < distanta[j]) && !viz[j]) {
                distanta[j]=cost[nod][j];
                tata[j]=nod;
            }
    }

    writer<<total<<endl;
    writer<<n-1<<endl;
    for(int i=2; i<=n; i++)
        writer<<i<<" "<<tata[i]<<endl;
    return 0;
}