//Algoritmul Krusksal
#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()
{
    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];
}
//grupa(x) returnneaza nodul cu care este asociat nodul x cu numarul cel mai mic posibil

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

    while (nr < n - 1) {
        a = v[k].x;
        b = v[k].y;
        grupa_a = grupa(viz[a]);
        grupa_b = grupa(viz[b]);
        if (grupa_a != grupa_b) {
            sol[nr++] = k;
            suma += v[k].cost;
            if (grupa_a < grupa_b)
                viz[b] = grupa_a;
            else
                viz[a] = grupa_b;
        }
        k++;
        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;
}