#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

const int MMAX  = 400001 ;
const int NMAX = 200001 ;

struct muchii
{
    int x ;
    int y ;
    int c ;
}v[MMAX] , aux ;


struct rezultat
{
    int x , y ;
}p[MMAX];

int n , m , k , rg[NMAX] , t[NMAX] , total ;

void citire ()
{
    fin >> n >> m ;
    for ( int i = 1 ; i <= m ; ++i )
    {
        fin >> v[i].x >> v[i].y >> v[i].c ;
    }
    for ( int i = 1 ; i <= n ; ++i )
    {
        t[i] = i ;
        rg[i] = 1 ;
    }
}

bool Compare(muchii a, muchii b)
{
    return a.c < b.c;
}


int pivot(int st,int dr)
{
    int p,q ;
    muchii x ;
    p=st; q=dr;
    x = v[p];
    while(p<q)
    {
        while(p<q&&v[q].c>=x.c)
            q--;
        v[p]=v[q];
        while(p<q&&v[p].c<x.c)
            p++;
        v[q]=v[p];
    }
    v[p]=x;
    return p;
}

void qsort(int st,int dr)
{
    int m;
    if(st<dr)
    {
        m=pivot(st,dr);
        qsort(st,m-1);
        qsort(m+1,dr);
    }
}

int gasire_tata ( int nod )
{
    while ( nod != t[nod] )
        nod = t[nod] ;
    return nod ;
}

void unire ( int x , int y )
{
  if(rg[x] < rg[y])
        t[x] = y;
    if(rg[y] < rg[x])
        t[y] = x;
    if(rg[x] == rg[y])
    {
        t[x] = y;
        rg[y]++;
    }
}

void rezolvare ( )
{
    for ( int i = 1 ; i <= m ; ++i )
    {
        int xt , yt ;
        xt = gasire_tata( v[i].x ) ;
        yt = gasire_tata( v[i].y ) ;
        if ( xt != yt )
        {
            unire( xt , yt );
            p[++k].x = v[i].x ;
            p[k].y = v[i].y ;
            total += v[i].c ;
        }
    }
}

int main()
{
    citire() ;
    qsort( 1 , m ) ;
    rezolvare();
    for ( int i = 1 ; i <= m ; ++i ) cout << v[i].x << " " << v[i].y << " " << v[i].c << '\n' ;
    fout<< total << '\n' ;
    fout << n - 1 << '\n' ;
    for ( int i = 1 ; i <= k; ++i )
    {
        fout << p[i].x << " " << p[i].y << '\n' ;
    }
    return 0;
}