#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;

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

struct aha{int x,y,cost;}c[400001];

bool cmp(aha q, aha w)
{
    if(q.cost>w.cost)return false;
    return true;
}

int main()
{
    int n,m,x,y,i,cost=0,cc[200001],nr=1,k=1,z=0,v[4001];
    fin>>n>>m;
    for(i=1; i<=m; i++)
        fin>>c[i].x>>c[i].y>>c[i].cost;
    sort(c+1,c+m+1,cmp);

    for(i=1;  i<=n; i++) cc[i]=i;

    while(nr<n)
    {
        x=c[k].x;
        y=c[k].y;
        if(cc[x]!=cc[y]) {
            z++;
            v[z]=k;
            cost+=c[k].cost;
            for(i=1; i<=n; i++){
                if(cc[i]==cc[x])
                    cc[i]=cc[y];
                fout<<cc[i]<<" ";
            }
            fout<<endl;
            nr++;
            }
        k++;
    }
    fout<<cost<<endl<<z<<endl;
    for(i=1; i<=z; i++) fout<<c[v[i]].x<<" "<<c[v[i]].y<<endl;

    return 0;
}