#include <bits/stdc++.h>

using namespace std;
const int INF = 0x3f3f3f3f;
int d[200001], p[200001];
vector<pair<int, int>> adj[200001];
bool viz[200001];
int N, M;
long long cost_total=0;
priority_queue<pair<int, int>> pq;
ifstream f("apm.in");
ofstream g("apm.out");

int main() {
    f>>N>>M;
    for (int i=0; i<M; i++) {
        int x,y,c;
        f>>x>>y>>c;
        adj[x].push_back({y, c});
        adj[y].push_back({x, c});
    }
    for (int i = 1; i <= N; i++) {
        d[i]=INF;
        viz[i]=false;
        p[i]=0;
    }
    int nod_start=1;
    d[nod_start]=0;
    pq.push({-d[nod_start], nod_start});

    while (!pq.empty()) {
        int cost_curent_neg= pq.top().first;
        int u = pq.top().second;
        pq.pop();
        int cost_curent=-cost_curent_neg;

        if (viz[u])
            continue;

        viz[u] = true;
        cost_total += cost_curent;
        for (pair<int, int>& muchie : adj[u]) {
            int v = muchie.first;
            int cost_muchie = muchie.second;
            if (!viz[v] && d[v] > cost_muchie) {
                d[v] = cost_muchie;
                p[v] = u;
                pq.push({-d[v], v});
            }
        }
    }

    g<<cost_total<<"\n";
    g<<N-1<<"\n";
    for (int i = 2; i <= N; ++i) {
         g<<i<<" "<<p[i]<<"\n";
    }
    f.close();
    g.close();
    return 0;
}