#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

const int NMAX = 200001;
const int MMAX = 400001;

struct muchie
{
    int i, j, cost;
};

int tata[NMAX], n, m, s, k;

muchie mu[MMAX], a[MMAX];

int radacina(int a)
{
    if(tata[a] == a)
    {
        return a;
    }
    tata[a] = radacina(tata[a]);
    return tata[a];
}

void unire(int a, int b)
{
    tata[a] = tata[b];
}

bool comp(muchie a, muchie b)
{
    return a.cost < b.cost;
}

void citire()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> mu[i].i >> mu[i].j >> mu[i].cost;
    }
}

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

    for(int i = 1; i <= m; i++)
    {
        int ai = radacina(mu[i].i);
        int aj = radacina(mu[i].j);
        if(ai != aj)
        {
            s += mu[i].cost;
            a[++k] = mu[i];
            unire(ai, aj);
        }

    }
}

void afisare()
{
    fout << s << '\n' << k << '\n';
    for(int i = 1; i <= k; i++)
    {
        fout << a[i].i << ' ' << a[i].j << '\n';
    }
    for(int i = 1; i <= n; i++)
    {
        cout << tata[i] << ' ';
    }
}

int main()
{
    citire();
    sort(mu + 1, mu + m + 1, comp);
    kruskal();
    afisare();
    return 0;
}