#include <bits/stdc++.h>
#define Nmax 400005
using namespace std;

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

int N, M, ans;
bool is[Nmax];

struct edge{
    int x, y, c;
};
edge v[Nmax];
bool cmp(edge a, edge b) {
    return a.c < b.c;
}

int t[Nmax / 2], h[Nmax / 2];
int root(int x) {
    while (t[x]) x = t[x];
    return x;
}
void unite(int x, int y) {
    if (h[x] > h[y]) swap(x, y);
    t[y] = x;
    if (h[x] == h[y]) h[x]++;
}
int main()
{
    fin >> N >> M;
    for (int i = 1; i <= M; ++i) {
        int x, y, c;
        fin >> x >> y >> c;
        v[i] = {x, y, c};
    }
    sort(v + 1, v + M + 1, cmp);

    for (int i = 1; i <= M; i++) {
        int x = root(v[i].x), y = root(v[i].y);
        if (x == y) continue;
        unite(x , y);
        ans += v[i].c;
        is[i] = 1;
    }

    fout << ans << '\n' << N - 1 << '\n';
    for (int i = 1; i <= M; ++i)
       if (is[i]) fout << v[i].x << " " << v[i].y << '\n';
    return 0;
}