#include <iostream>
#include <fstream>
#include <vector>
#include <utility> //pt pair
#include <set>  //ca sa pastram sortat perechile
using namespace std;

struct comparare
{
bool operator()(const pair<pair<int,int>, int>&i, const pair<pair<int,int>, int>&j)
const{
    if(i.second<j.second)
        return 1;
    else if(i.second==j.second && i.first.second<j.first.second)
        return 1;
    else if(i.second==j.second && i.first.second==j.first.second && i.first.first<j.first.first)
        return 1;
    else
        return 0;
    }
};

multiset<pair< pair<int,int>,int>,comparare> date,apcm;
multiset<pair< pair<int,int>,int> > ::iterator it;
vector<int>::iterator v_it;
int main()
{
    int N,M,x,y,z,muchie_cost_minim;
    pair<int,int> temp;
    ifstream f("apm.in");
    ofstream g("apm.out");
    f>>N>>M;
    vector<int> culori_componente;
    for(int i=0;i<=N;i++)
    {
        culori_componente.push_back(i);
    }
    for(int i=1;i<=M;i++)
    {
        f>>x>>y>>z;
        temp=make_pair(x,y);
        date.insert(make_pair(temp,z));
    }
  /// for(it=date.begin();it!=date.end();++it)
  ///     cout<<(*it).first.first<<" "<<(*it).first.second<<"\n";
    ///KRUSKAL
    for(it=date.begin();it!=date.end();++it)
    {
        muchie_cost_minim=(*it).second;
        x=(*it).first.first;
        y=(*it).first.second;
        ///cout<<"\n"<<x<<" col_x: "<<culori_componente[x]<<"... "<<y<<" col_y: "<<culori_componente[y]<<" "<<muchie_cost_minim<<" ";
        if(culori_componente[x]<culori_componente[y])
            {
                for(int i=1;i<=N;i++)
                    {
                    ///cout<<"\n("<<i<<" "<<y<<")"<<culori_componente[i]<<" "<<culori_componente[y]<<endl;
                    if(culori_componente[i]==culori_componente[y] && i!=y)
                        culori_componente[i]=culori_componente[x];

                    }
                    culori_componente[y]=culori_componente[x];
                apcm.insert(make_pair(make_pair(x,y),muchie_cost_minim));
                ///cout<<"\nAfter insertion into apcm\n";
                ///cout<<"\n"<<x<<" col_x: "<<culori_componente[x]<<"... "<<y<<" col_y: "<<culori_componente[y]<<" "<<muchie_cost_minim<<" \n\n";
            }
        else if(culori_componente[x]>culori_componente[y])
        {
            for(int i=1;i<=N;i++)
                    {
                    if(culori_componente[i]==culori_componente[x] && i!=x)
                        culori_componente[i]=culori_componente[y];

                    }
                    culori_componente[x]=culori_componente[y];
                apcm.insert(make_pair(make_pair(x,y),muchie_cost_minim));
                ///cout<<"\nAfter insertion into apcm\n";
                ///cout<<"\n"<<x<<" col_x: "<<culori_componente[x]<<"... "<<y<<" col_y: "<<culori_componente[y]<<" "<<muchie_cost_minim<<" \n\n";
        }
        for(v_it=culori_componente.begin();v_it!=culori_componente.end();v_it++)
            cout<<*v_it<<" ";
            cout<<"\n";
    }
    ///AFISARE COST APCM
    int cost_apcm=0,NUMAR_MUCHII_APCM=0;
    for(it=apcm.begin();it!=apcm.end();++it)
        {
            cost_apcm+=(*it).second;
            NUMAR_MUCHII_APCM++;
        }
    g<<cost_apcm<<endl;
    ///MUCHII ARBORE APCM
    g<<NUMAR_MUCHII_APCM<<endl;
    ///LISTARE MUCHII
    for(it=apcm.begin();it!=apcm.end();++it)
        g<<(*it).first.first<<" "<<(*it).first.second<<endl;


    return 0;
}