#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define pii pair<int, int>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

const int NMAX = 2e5 + 5, inf = 1e9;
const char nl = '\n';
vector<pii> g[NMAX], muchii;
int visitat[NMAX],parent[NMAX], dist[NMAX], cost = 0;

void prim (int source, int n) {
    for (int i = 1; i <= n;i++) dist[i] = inf;
    dist[source] = 0;
    priority_queue<pii> pq;
    pq.push({0, source});
    while (!pq.empty()) {
        int nod = pq.top().second;
        int lun = -pq.top().first;
        pq.pop();
        if (visitat[nod]  == 1) continue;
        visitat[nod] = 1;
        if (lun < dist[nod]) {
            cost += lun;
            muchii.push_back({nod, parent[nod]});
        }
      


        for (auto neigh: g[nod]) {
            if (visitat[neigh.first] == 0) {
                parent[neigh.first] = nod;
                pq.push({-neigh.second, neigh.first});
            }
        }
    }
}




int main () {
    int n, m, x, y, z;
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        fin >> x >> y >> z;
        g[x].push_back({y, z});
        g[y].push_back({x, z});
    }
    prim(1, n);
    fout << cost << nl;
    fout << muchii.size() << nl;
    for (auto it: muchii) {
        fout << it.first << " " << it.second << nl;
    }

}