#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define maxN 200002
using namespace std;
int n, i, j, m, sol, nre, t[maxN];
struct edge
{
    int x;
    int y;
    int z;
}el;
struct esol
{
    int a;
    int b;
}q[maxN];
vector < edge > V;
int cmp(const edge a, const edge b)
{
    return a.z > b.z;
}
int root(int x)
{
    if (t[x] == 0)
        return x;
    t[x] = root(t[x]);
    return t[x];
}
void Union(int x, int y)
{
    int rx = root(x), ry = root(y);
    t[rx] = ry;
}
void read()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for (i = 1; i <= m; ++ i)
    {
        scanf("%d %d %d", &el.x, &el.y, &el.z);
        V.push_back(el);
    }
}
void solve()
{
    int rx, ry;
    sort(V.begin(), V.end(), cmp);
    while (m --)
    {
        el = V.back();
        rx = root(el.x);
        ry = root(el.y);
        if (rx != ry)
        {
            Union(el.x, el.y);
            sol += el.z;

            q[++ nre].a = el.x;
            q[nre].b = el.y;
        }
        V.pop_back();
    }
}
void write()
{
    freopen("apm.out", "w", stdout);
    printf("%d\n%d\n", sol, nre);
    for (i = 1; i <= nre; ++ i)
        printf("%d %d\n", q[i].a, q[i].b);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}