#include <bits/stdc++.h>
#include <fstream>

using namespace std;

ifstream f("apm.in");
ofstream f2("apm.out");

int graph[600][600], key[400001], parent[400001], n, m, i, j, x, y, cost, sum = 0, c;
bool mstSet[400001];

int minKey(int key[], bool mstSet[]){
    int min = INT_MAX;
    int min_index;

    for(i = 1; i <= n; i++){
        if(mstSet[i] == false && key[i] < min){
            min = key[i];
            min_index = i;
        }
    }
    return min_index;
}

void primMst(int graph[600][600]){
    for(i = 1; i <= n; i++){
        key[i] = INT_MAX;
        mstSet[i] = false;
    }

    key[1] = 0;
    parent[1] = 0;

    for(c = 1; c < n; c++){
        int u = minKey(key, mstSet);
        mstSet[u] = true;
        for(int a = 1; a <= n; a++){
            if(graph[u][a] != 0 && mstSet[a] == false && graph[u][a] < key[a]){
                parent[a] = u;
                key[a] = graph[u][a];
            }
        }
    }
}

void print(int parent[], int graph[600][600]){
    for(i = 2; i <= n; i++){
        f2 << parent[i] << " " << i << endl;
    }
}


int main()
{
    f >> n >> m;

    for(i = 1; i <= n; i++){
        for(j = 1; j <= n; j++){
            graph[i][j] = 0;
        }
    }

    for(i = 1; i <= m; i++){
        f >> x >> y >> cost;
        graph[x][y] = cost;
        graph[y][x] = cost;
    }

    primMst(graph);
    for(i = 1; i <= n; i++){
        sum = sum + key[i];
    }

    f2 << sum << endl;
    f2 << n - 1 << endl;
    print(parent, graph);

    return 0;
}