#include <iostream>
#include<fstream>
#include<queue>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie
{
    int i, j, c;

};
class cmpMuchie
{
public:
    bool operator()(const muchie& a, const muchie& b)
    {
        return a.c > b.c;
    }
};
int n, m, cost;
priority_queue<muchie, vector<muchie>, cmpMuchie> M;
vector<muchie> sol;
int cc[200001];
void citire()
{
    muchie mm;
    f >> n >> m;
    for(int i = 1; i <= m; i++)
        {f >> mm.i >> mm.j >> mm.c;
    M.push(mm);}
}
int grupa(int i)
{
    if(cc[i] == 0)
        return i;
    cc[i] = grupa(cc[i]);
    return cc[i];
}
void kruskal()
{
    unsigned  n1 = n - 1;
    while(sol.size() < n1)
    {
        muchie mm = M.top();
        M.pop();
        int gi = grupa(mm.i);
        int gj = grupa(mm.j);
        if(gi != gj)
        {
            cost += mm.c;
            cc[gi] = gj;
            sol.push_back(mm);
        }
    }
}
void afis()
{
    g << cost << '\n' << n - 1 << '\n';
    for(unsigned  i = 0; i < sol.size(); i++)
        g << sol[i].i << ' ' << sol[i].j << '\n';
}
int main()
{
    citire();
    kruskal();
    afis();
    for(int i=1;i<=n;i++)
        cout<<cc[i]<<' ';
    return 0;
}