#include <bits/stdc++.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
const int inf = 1e9 + 7;

int n, m, x, y, c;
vector <pair<int, int>> v[200005];
vector <int> d(200005, inf);
vector <int> t(200005, -1);
vector <bool> inArb(200005, false);

// (cost, nod)
priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

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

    int cost_min = 0;
    int taken = 0;
    pq.push (make_pair(0, 1));

    while (!pq.empty()&& taken < n) {
        pair<int, int> k = pq.top();
        pq.pop();

        if (inArb[k.second] == false) {
            inArb[k.second] = true;
            cost_min += k.first;
            taken++;

            for (auto x: v[k.second]) {
                if (inArb[x.first] == false && x.second < d[x.first]) {
                    t[x.first] = k.second;
                    d[x.first] = x.second;
                    pq.push ({d[x.first], x.first});
                }
            }
        }
    }

    g << cost_min << '\n' << taken-1 << '\n';
    for (int i=2; i<=n; ++i) {
        g << i << ' ' << t[i] << '\n';
    }
    return 0;
}