#include <iostream>
#include <vector>
#include <queue>
#include <fstream>

using namespace std;


vector<pair<int,int>> L[200001];
int d[200001], p[200001], vis[200001];

int main() {

    ifstream fin("apm.in");
    ofstream fout("apm.out");
    
    int n,m;
   fin>> n >> m;
    for (int i = 1; i <= m; i ++) {
        int x, y, c;
       fin>> x >> y >> c;
        L[x].push_back({y, c});
        L[y].push_back({x, c});
    }

    for (int i = 1; i <= n; i ++) {
        d[i] = 1e9;
    }

    d[1] = 0;
    int sum = 0;
    priority_queue<pair<int, int>> pq;// (d[nod], nod)
    pq.push({-d[1], 1});

    while(pq.empty() == false) {
        int nod = pq.top().second;
        pq.pop();
        if (vis[nod] == 1) {
            continue;
        }

        sum += d[nod];
        vis[nod] = 1;
        for(auto it : L[nod]) {
            int vec = it.first;
            int cost = it.second;

            if(vis[vec] == 0 && d[vec] > cost) {
                d[vec] = cost;
                p[vec] = nod;
                pq.push({-d[vec], vec});
            }
        }
    }

   fout<< sum << "\n";
   fout<< n - 1 << "\n";
    for (int i = 2; i <= n; i ++ ){
       fout<< i << " " << p[i] << '\n';
    }

}