#include <stdio.h>
#include <vector>
#include <queue>
#define INF 1001
#define N 200000

std::vector <std::pair <int, int>> g[1 + N];
std::priority_queue <std::pair <int, int>, std::vector <std::pair <int, int>>, std::greater <std::pair <int, int>>> q;
bool inApm[1 + N];
int cost[1 + N], parent[1 + N];
int n;

int main() {
    FILE *fin, *fout;
    int m, x, y, c, nod;

    fin = fopen("apm.in", "r");
    fscanf(fin, "%d%d", &n, &m);
    for ( int i = 0; i < m; i ++ ) {
        fscanf(fin, "%d%d%d", &x, &y, &c);
        g[x].push_back({y, c});
        g[y].push_back({x, c});
    }
    fclose(fin);

    for ( int i = 1; i <= n; i ++ ) {
        inApm[i] = false;
        cost[i] = INF;
    }

    q.push({0, 1});
    cost[1] = -INF;
    while ( !q.empty() ) {
        nod = q.top().second;
        q.pop();
        if ( !inApm[nod] ) {
            inApm[nod] = true;
            for ( std::pair<int, int> v : g[nod] ) {
                if ( !inApm[v.first] && cost[v.first] > v.second ) {
                    cost[v.first] = v.second;
                    parent[v.first] = nod;
                    q.push(std::make_pair(v.second, v.first));
                }
            }
        }
    }

    int sum = 0;
    for ( int i = 2; i <= n; i ++ )
        sum += cost[i];

    fout = fopen("apm.out", "w");
    fprintf(fout, "%d\n%d\n", sum, n - 1);
    for ( int i = 2; i <= n; i ++ )
        fprintf(fout, "%d %d\n", parent[i], i);
    fclose(fout);
    return 0;
}