#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in ("apm.in");
ofstream out ("apm.out");
int n,m,parent[200002],cost,nrm;
struct muchie
{
    int x,y,z;
}a[400002],sol[200002];
bool comp (muchie b,muchie c)
{
    if (b.z<c.z) return true;
    else
    {
        if (b.x<c.x) return true;
        return false;
    }
}
int find (int x)
{
    if (parent[x]!=x)
        parent[x]=find(parent[x]);
    return parent[x];
}
void unionn (int x,int y)
{
    int xroot=find(x);
    int yroot=find(y);
    if (xroot!=yroot)
    {
        parent[xroot]=parent[yroot];
    }
}
int main()
{
    in>>n>>m;
    int x,y;
    for (int i=1;i<=m;i++)
    {
        in>>a[i].x>>a[i].y>>a[i].z;
    }
    sort (a+1,a+m+1,comp);
    for (int i=1;i<=m;i++)
    {
        cout<<a[i].x<<' '<<a[i].y<<' '<<a[i].z<<'\n';
    }
    for (int i=1;i<=n;i++) parent[i]=i;
    int i=1;
    while (n-1)
    {
        x=find (a[i].x);
        y=find (a[i].y);
        if (x!=y)
        {
            cost+=a[i].z;
            n--;
            nrm++;
            sol[nrm].x=a[i].x;
            sol[nrm].y=a[i].y;
            unionn (a[i].x,a[i].y);
        }
        i++;
    }
    out<<cost<<'\n'<<nrm<<'\n';
    for (int i=1;i<=nrm;i++)
    {
        out<<sol[i].x<<' '<<sol[i].y<<'\n';
    }
    return 0;
}