#include <iostream>
#include <fstream>

using namespace std;

int INF = 10000;

struct muchie{
    int i;
    int j;
};

int main(){
    ifstream f("apm.in");
    ofstream of("apm.out");
    int x,y,cost;
    int n,m;
    f >> n >> m;
    int a[n+1][n+1];
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            a[i][j] = INF;
        }
    }
    for(int i = 1;i<=m;i++){
        f >> x >> y >> cost;
        a[x][y] = cost;
        a[y][x] = cost;
    }
    int nod_start = 1;
    int t[n+1];
    bool viz[n+1];
    for(int i = 1;i<=n;i++){
        t[i] = nod_start;
        viz[i] = false;
    }
    t[nod_start] = 0;
    viz[nod_start] = 1;
    int mn;
    int nod_min_x, nod_min_y;
    int s = 0;
    muchie sol[n+1];
    int nsol = 0;
    for(int k = 1;k<=n-1;k++){
        mn = INF;
        nod_min_x = 0;
        nod_min_y = 0;
        for(int i = 1;i<=n;i++){
            if(viz[i]){
                for(int j = 1;j<=n;j++){
                    if(!viz[j] && a[i][j] < mn){
                        mn = a[i][j];
                        nod_min_x = i;
                        nod_min_y = j;
                    }
                }
            }
        }
        if(mn == INF){
            break;
        }
        viz[nod_min_y] = 1;
        s = s + mn;
        //cout << nod_min_x << " " << nod_min_y << endl;
        nsol++;
        sol[nsol].i = nod_min_x;
        sol[nsol].j = nod_min_y;
    }
    of << s << endl;
    of << nsol << endl;
    for(int i = 1;i<=nsol;i++){
        of << sol[i].i << " " << sol[i].j << endl;
    }
}