//#include <fstream>
//#include <vector>
//#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int rx,ry,T[200001],s,aux,viz[200001];

struct edge
{
    int x,y,w;
    edge() {x=0,y=0,w=0;}
    edge(int a, int b, int c): x(a),y(b),w(c){}
};
vector<edge> v;

int valid(int x, int y)
{
    rx=x;
    while(T[rx]!=0)
    {
        rx=T[rx];
    }
    while(x!=rx)
    {
        aux=x;
        x=T[x];
        T[aux]=rx;
    }
    ry=y;
    while(T[ry]!=0)
    {
        ry=T[ry];
    }
    while(y!=ry)
    {
        aux=y;
        y=T[y];
        T[aux]=ry;
    }
    cout<<rx<<" "<<ry<<'\n';
    if(rx!=ry)
    {
        T[rx]=ry;
    }
    return rx!=ry;
}

int main()
{
    int n,m,x,y,w;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>w;
        v.push_back(edge(x,y,w));
    }
    sort(v.begin(),v.end(),[](edge a, edge b) {return a.w < b.w;} );
    for(int i=0;i<m;i++)
    {
        if(valid(v[i].x,v[i].y))
        {
            viz[i]=1;
            s+=v[i].w;
        }
        cout<<v[i].x<<" "<<v[i].y<<" "<<s<<'\n';
    }
    fout<<s<<'\n'<<n-1<<'\n';
    for(int i=0;i<m;i++)
    {
        if(viz[i]!=0)
        {
            fout<<v[i].x<<" "<<v[i].y<<'\n';
        }
    }
    return 0;
}