#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

struct muchie{
    int x,y,c;
};

muchie v[400000];




int p[200000];

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

int findSet(int x){
   if (p[x]==x){
        return x;
   }
   return p[x]=findSet(p[x]);
}

bool insameSet(int x, int y){
    return (findSet(x)==findSet(y));
}

void unionSet(int x,int y){
    if (!insameSet(x,y)){
        int a=findSet(x);
        int b=findSet(y);
        p[a]=b;
    }
}

int main()
{
    int n,m,i,j,x,y,lungime;
    ifstream f("apm.in");
    ofstream g("apm.out");
    f >> n >> m;
    lungime=0;
    cout << m << "\n";
    for (i=1;i<=m;i++){
        f >> v[i].x >> v[i].y>> v[i].c;
        cout <<  v[i].x << " " <<  v[i].y << " "  << v[i].c << "\n" ;
    }
    for(i=1;i<=n;i++){
        p[i]=i;
    }
    n=0;
    sort(v+1,v+m+1,comp);
    cout << "\n";
    for (i=1;i<=m;i++)
    cout <<  v[i].x << " " <<  v[i].y << " "  << v[i].c <<  "\n" ;
    for(i=1;i<=m;i++){
        x=v[i].x;
        y=v[i].y;
        if (!insameSet(x,y)){
            n++;
            unionSet(x,y);
            lungime=lungime+v[i].c;
            v[n].x=x;
            v[n].y=y;
        }
    }
    g << lungime << "\n";
    g << n << "\n";
    for (i=1;i<=n;i++){
        g << v[i].x << " " << v[i].y << "\n";

    }
}