#include <iostream>
#include <bits/stdc++.h>

using namespace std;

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

int n,m;
vector<pair<int, int>> la[200001];
bool viz[200001];

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

    // incep cu nod 1
    priority_queue<pair<int, int>> pq;
    pq.push({0, 1});

    int parent = 0;
    int cnt = 0;
    vector<pair<int, int>> ret;
    int sum = 0;

    while (pq.size()) {
        auto [cost, from] = pq.top();
        pq.pop();
        if (viz[from])
            continue;
        viz[from] = true;
        cnt ++;
        sum -= cost;

        if (parent != 0) {
            ret.push_back({parent, from});
        }

        parent = from;

        for (auto [to, c2]: la[from]) {
            if (viz[to])
                continue;
            pq.push({-c2, to});
        }
    }
    cnt --;

    out << sum << '\n' << cnt << '\n';
    for (auto [from, to]: ret)
        out << from << ' ' << to << '\n';

    return 0;
}