#include <bits/stdc++.h>

using namespace std;

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

const int N = 2e5 + 1, INF = 2000;
int n, m, x, y, cost, pred[N], d[N], tcost;
vector<pair<int, int>> c[N];
bool selectat[N];

void prim(int start){
    for(int i = 1; i <= n; i++)
        d[i] = INF;

    d[start] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
    heap.push({0, start});
    while(!heap.empty()){
        int x = heap.top().second;
        heap.pop();
        if(selectat[x])
            continue;

        tcost += d[x]; // aici se calculeaza, in afara while-ului nu merge!
        selectat[x] = 1;
        for(auto e: c[x]){
            int y = e.first, cost = e.second;
            if(d[y] > cost){
                d[y] = cost;
                pred[y] = x;
                heap.push({cost, y});
            }
        }
    }
}

int main(){
    f >> n >> m;
    for(int i = 0; i < m; i++){
        f >> x >> y >> cost;
        c[x].push_back({y, cost});
        c[y].push_back({x, cost});
    }

    f.close();
    prim(1);
    g << tcost << '\n' << n - 1 << '\n';
    for(int i = 2; i <= n; i++) // i porneste de la 2 pt. ca avem n - 1 muchii
        g << i << ' ' << pred[i] << '\n';

    g.close();
}