#include <bits/stdc++.h>

using namespace std;

const int NMAX = 2e5;
int p[NMAX + 5],pozans[NMAX + 5];
struct Edge {
    int a,b,c;
}edges[2 * NMAX + 5];

bool cmp(Edge e1, Edge e2) {
    return e1.c < e2.c;
}
int parent(int x) {
    if (!p[x])
        return x;
    p[x] = parent(p[x]);
    return p[x];
}
void join(int x, int y) {
    p[parent(x)] = parent(y);
}
int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    int n,m,ans = 0,cnt = 0;
    fin >> n >> m;
    for (int i = 0;i < m;i++)
        fin >> edges[i].a >> edges[i].b >> edges[i].c;
    sort(edges, edges + m, cmp);
    for (int i = 0;i < m;i++) {
        if (parent(edges[i].a) != parent(edges[i].b)) {
            pozans[cnt++] = i;
            ans += edges[i].c;
            join(edges[i].a, edges[i].b);
        }
    }
    fout << ans << '\n' << cnt << '\n';
    for (int i = 0;i < cnt;i++)
        fout << edges[pozans[i]].a << " " << edges[pozans[i]].b << '\n';
    return 0;
}