#include <bits/stdc++.h>

#define mx 400005
#define N 200005
using namespace std;
int n, m, t[N], h[N], C;
vector<int> r;
struct edge {
    int x, y, c;
} M[mx];

bool cmp(edge a, edge b)
{
    return a.c < b.c;
}

int root(int n)
{
    while (t[n]) n = t[n];
    return n;
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    int i, a, b, j;
    scanf("%i%i", &n, &m);
    for (i = 1; i <= m; i++)
        scanf("%i%i%i", &M[i].x, &M[i].y, &M[i].c);
    sort(M + 1, M + m + 1, cmp);

    j = 0;
    for (i = 1; i < n; i++) {
        do {
            a = root(M[++j].x);
            b = root(M[j].y);
        } while (a == b);

        C += M[j].c;
        r.push_back(j);

        if (h[a] > h[b]) t[b] = a;
        else if (h[a] < h[b]) t[a] = b;
        else {
            t[a] = b;
            h[b]++;
        }
    }

    printf("%i\n%i\n", C, r.size());
    for (auto x:r) printf("%i %i\n", M[x].x, M[x].y);
    return 0;
}