#include <iostream>
#include <fstream>
#include <algorithm>
#include <map>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int tata[200000];
struct ele
{
    int x,y,c,e;
};
bool cmp(struct ele a,struct ele b)
{
    if (a.c<b.c)
        return true;
    return false;
}
int gr(int x);
void miau(int x,int y)
{
    tata[gr(x)] = tata[gr(y)];
}
int main()
{
    int n,m,i,j;
    in>>n>>m;
    struct ele v[m+1];
    int frec[n+1];
    for(i=1;i<=n;i++)
        frec[i] = 0;
    for(i=1;i<=n;i++)
        tata[i]=i;
    struct ele ao;
    for(i=1;i<=m+1;i++)
        v[i].e =3;
    for(i=1;i<=m;i++)
    {
        in>>ao.x;
        in>>ao.y;
        in>>ao.c;
        v[i] = ao;
        v[i].e = 0;
    }
    sort(v+1,v+m+1,cmp);
    int costul=0,nr=0;
    int ambgnm = 0;
    for(i = 1;(i<=m && nr!=n);i++)
    {
        if (gr(v[i].x)!= gr(v[i].y))
        {
            frec[++nr] = i;
            miau(v[i].x,v[i].y);
            costul +=v[i].c;
        }
        else
          v[i].e = 1;
    }
    out<<costul<<"\n";
    out<<nr<<"\n";
    for(i=1;i<=nr;i++)
            out<<v[frec[i]].x<<" "<<v[frec[i]].y<<" "<<"\n";
    return 0;
}
int gr(int x)
{
    if (tata[x]==x)
        return x;
    else
        gr(tata[x]);
}