#include <cstdio>
#include <algorithm>

using namespace std;

int n,m,a[400000],b[400000],c[400000],ind[400000],cost=0,nr=0,y[400000],z[400000];
struct nod{ int parinte,rang;} x[400000];

void citire()
{
    FILE *f=fopen("apm.in","r");
    fscanf(f,"%i %i",&n,&m);
    for(int i=0;i<m;i++)
        fscanf(f,"%i %i %i",&a[i],&b[i],&c[i]);
}

int comp(int i,int j)
{
    return(c[i]<c[j]);
}

int find_set(int i)
{
    if (x[i].parinte!=i)
        x[i].parinte=find_set(x[i].parinte);
    return x[i].parinte;
}

void uniune(int a,int b)
{
    int a_root=find_set(a),b_root=find_set(b);
    if(x[a_root].rang>x[b_root].rang)
    {
        x[b_root].rang++;
        x[b_root].parinte=a_root;
    }
    else
        if(x[a_root].rang<x[b_root].rang)
        {
            x[a_root].rang++;
            x[a_root].parinte=b_root;
        }
        else
        {
            x[a_root].parinte=b_root;
            x[b_root].rang++;
        }
}

int main()
{
    citire();
    for(int i=0;i<m;i++)
    {
        ind[i]=i;
        x[i].parinte=i;
        x[i].rang=0;
    }
    sort(ind,ind+m,comp);
    for(int i=0;i<m;i++)
    {
        printf("%i %i %i\n",a[ind[i]],b[ind[i]],c[ind[i]]);
    }
    for(int i=0;i<m;i++)
        if(find_set(a[ind[i]])!=find_set(b[ind[i]]))
        {
            cost+=c[ind[i]];
            y[nr]=a[ind[i]];
            z[nr]=b[ind[i]];
            nr++;
            uniune(a[ind[i]],b[ind[i]]);
        }
    FILE *g=fopen("apm.out","w");
    fprintf(g,"%i\n%i\n",cost,nr);
    for(int i=0;i<nr;i++)
        fprintf(g,"%i %i\n",y[i],z[i]);
    return 0;
}