#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <algorithm>

#define nod first
#define c second

using namespace std;

int n,nrm;
vector < list < pair < int, short > > > v;
vector < pair < int, list < pair < int, short > >::iterator > > m;
vector < int > a;
vector < pair < int, int > > sol;
long long C;

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

void citire()
{
    int i,x,y,c;
    in>>n>>nrm;
    v.resize(n+1);
    sol.reserve(n);
    for(i=1;i<=nrm;i++)
    {
        in>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
        v[y].push_back(make_pair(x,c));
    }
}

bool cmp(pair < int, list < pair < int, short > >::iterator > a, pair < int, list < pair < int, short > >::iterator > b)
{
    return (*(a.second)).second<(*(b.second)).second;
}

void kruskal()
{
    int i,j;
    list < pair < int, short > >::iterator it;
    vector < pair < int, list < pair < int, short > >::iterator > >::iterator k;
    m.reserve(nrm+1);
    a.resize(n+1);
    for(i=1;i<=n;i++)
    {
        a[i]=i;
        for(it=v[i].begin();it!=v[i].end();it++)
        {
            if((*it).nod>i)
                m.push_back(make_pair(i,it));
        }
    }
    sort(m.begin(),m.end(),cmp);
    k=m.begin();
    for(i=1;i<n;i++)
    {
        while(a[(*k).first]==a[(*((*k).second)).nod])
            k++;
        C+=(*((*k).second)).second;
        sol.push_back(make_pair((*k).first,(*((*k).second)).nod));
        cout<<sol[i-1].first<<' '<<sol[i-1].second<<'\n';
        for(j=1;j<=n;j++)
            cout<<a[j]<<' ';
        cout<<'\n';
        for(j=1;j<(*((*k).second)).nod;j++)
            if(a[j]==a[(*((*k).second)).nod])
                a[j]=a[(*k).nod];
        for(j++;j<=n;j++)
            if(a[j]==a[(*((*k).second)).nod])
                a[j]=a[(*k).nod];
        a[(*((*k).second)).nod]=a[(*k).nod];
        for(j=1;j<=n;j++)
            cout<<a[j]<<' ';
        cout<<"\n\n\n";
        k++;
    }

}

void afisare()
{
    out<<C<<'\n'<<n-1;
    for(int i=0;i<n-1;i++)
        out<<'\n'<<sol[i].first<<' '<<sol[i].second;

}

int main()
{
    citire();
    kruskal();
    afisare();
    return 0;
}