# include <bits/stdc++.h>

using namespace std;

const int Nmax = 1e5;

struct per {int x, y;};
per ans[Nmax * 4 + 5];
int n, m, t[Nmax * 2 + 5], rang[Nmax * 2 + 5], i, N, cost;

pair < int, pair <int, int> >  G[Nmax * 4 + 5];

int Find (int node)
{
    if (t[node] != node) t[node] = Find(t[node]);
    return t[node];
}

void unite(pair < int,  pair <int, int> > muchie)
{
    int a = Find(muchie.second.first), b = Find(muchie.second.second);

    if (a != b)
    {
        if (rang[a] > rang[b]) t[b] = a;
        else t[a] = b;
        if (rang[a] == rang[b]) rang[b]++;

        cost += muchie.first;
        ans[++N].x = muchie.second.first, ans[N].y = muchie.second.second;

    }
}

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

    scanf("%d %d\n", &n, &m);

    for (i = 1; i <= m; ++i)
        scanf("%d %d %d\n", &G[i].second.first, &G[i].second.second, &G[i].first);

    sort(G + 1, G + m + 1);

    for (i = 1; i <= n; ++i)
        t[i] = i, rang[i] = 1;

    for (i = 1; i <= m; ++i)
        unite(G[i]);

    printf("%d\n%d\n", cost, N);

    for (i = 1; i <= N; ++i)
        printf("%d %d\n", ans[i].x, ans[i].y);

    return 0;
}