#include <bits/stdc++.h>

using namespace std;

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

struct Edge {
    int x, y, z;
    bool operator < (const Edge &other) const {
        return z < other.z;
    }
} e[400005];
int n, m, k;

int t[200005];
pair <int, int> a[200005];

int f(int nod) {
    if(t[nod] == nod)
        return nod;
    return t[nod] = f(t[nod]);
}

int main()
{
    in >> n >> m;
    for(int i = 1; i <= m; i++) {in >> e[i].x >> e[i].y >> e[i].z;};
    for(int i = 1; i <= n; i++) t[i] = i;
    sort(e + 1, e + m + 1);
    int ans = 0;
    for(int i = 1; i <= m; i++) {
        int x = e[i].x, y = e[i].y;
        if(f(x) == f(y))
            continue;
        ans += e[i].z;
        t[f(e[i].x)] = f(e[i].y);
        a[++k] = {e[i].x, e[i].y};
    }
    out << ans << "\n" << k << "\n";
    for(int i = 1; i <= k; i++)
        out << a[i].first << " " << a[i].second << "\n";
    return 0;
}