#include <bits/stdc++.h>

using namespace std;
ifstream fin("in");
ofstream fout("out");
int tt[200001], sz[200001], n, m, cnt, suma;
struct muchie
{
    int x, y, cost;
}v[400001];

bool cmp(muchie x, muchie y)
{
    return x.cost < y.cost;
}

int Find(int nod)
{
    if (tt[nod] == nod)
        return nod;
    return tt[nod] = Find(tt[nod]);
}

void Union(int a, int b)
{
    if (a == b)
        return;
    if (sz[a] >= sz[b]) {
        sz[a] += sz[b];
        tt[b] = a;
    }
    else {
        sz[b] += sz[a];
        tt[a] = b;
    }
}

struct muchie2
{
    int a, b;
}w[200001];

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        fin >> v[i].x >> v[i].y >> v[i].cost;
    }
    for (int i = 1; i <= n; i++) {
        tt[i] = i;
        sz[i] = 1;
    }
    sort(v + 1, v + m + 1, cmp);
    for (int i = 1; i <= m; i++) {
        if (Find(v[i].x) != Find(v[i].y)) {
            suma += v[i].cost;
            Union(Find(v[i].x), Find(v[i].y));
            cnt++;
            w[cnt].a = v[i].x;
            w[cnt].b = v[i].y;
        }
    }
    fout << suma << "\n" << cnt << "\n";
    for (int i = 1; i <= n - 1; i++) {
        fout << w[i].a << " " << w[i].b << "\n";

    }

    return 0;
}