#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m, sum, val[200005];
vector < pair <int, int> > rez;
bool viz[200005];

struct comp {
    bool operator() (pair <int, int> a, pair <int, int> b) {
        return a.second > b.second;
    }
};

priority_queue < pair <int, int>, vector < pair <int, int> >, comp> pq;
vector < pair <int, int> > g[200005];

void solve(int nod) {
    viz[nod] = true;
    for (int i = 0; i < g[nod].size(); ++i) {
        int next = g[nod][i].first, nr = g[nod][i].second;
        if (viz[next])
            continue;
        if (val[next] == 1e6 || nr < val[next]) {
            val[next] = nr;
            pq.push({next,nr});
        }
    }
    while (!pq.empty() && (viz[pq.top().first] || val[pq.top().first] != pq.top().second))
        pq.pop();
    if (!pq.empty()) {
        int el = pq.top().first;
        rez.push_back({nod, el});
        sum += val[el];
        pq.pop();
        solve(el);
    }
    return;
}

int main() {
    fin >> n >> m;
    for (int i = 1; i <= n; ++i)
        val[i] = 1e6;
    for (int i = 1; i <= m; ++i) {
        int a, b, c;
        fin >> a >> b >> c;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }
    solve(1);
    fout << sum << "\n" << rez.size() << "\n";
    for (int i = 0; i < rez.size(); ++i)
        fout << rez[i].first << " " << rez[i].second << "\n";
    return 0;
}