#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define MAXM 400000
#define MAXN 200001
using namespace std;

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

struct muchie
{
    int x, y, cost;
};
muchie v[MAXM];

int n, m, nr, viz[MAXN], sol[MAXN], k;
long long suma;

void read()
{
    int a, b;

    fin >> n >> m;
    for (int i = 0; i < m; ++i) {
        fin >> v[i].x >> v[i].y >> v[i].cost;
    }
}

bool cmp(muchie a, muchie b)
{
    if (a.cost <= b.cost)
        return true;
    return false;
}

void init()
{
    for (int i = 1; i <= n; ++i)
        viz[i] = i;
}

int grupa(int val)
{
    if (viz[val] == val)
        return val;
    viz[val] = grupa(viz[val]);
    return viz[val];
}

void solve()
{
    int a, b, aux;

    while (nr < n - 1) {
        a = v[k].x;
        b = v[k].y;
        k++;
        if (grupa(a) != grupa(b)) {
            sol[nr++] = k - 1;
            suma += v[k - 1].cost;
            if (grupa(a) < grupa(b)) {
                viz[b] = grupa(a);
            }
            else {
                viz[a] = grupa(b);
            }
        }
        for (int i = 1; i <= n; ++i)
            cout << viz[i] << ' ';
        cout << "\n\n";
    }
}

void write()
{
    int aux;

    fout << suma << '\n' << n - 1 << '\n';
    for (int i = 0; i <= n - 2; ++i) {
        aux = sol[i];
        fout << v[aux].x << ' ' << v[aux].y << '\n';
    }
}

int main()
{
    read();
    init();
    sort(v, v + m, cmp);
    solve();
    write();
    return 0;
}