#include <bits/stdc++.h>
#define NMAX 400001
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct nod
{
    int x,y,c;
} v[NMAX];
bool cmp(nod a,nod b)
{
    return a.c<b.c;
}
int tata[NMAX],s,n,m,i,j,ct,val1,val2;
bool viz[NMAX];
int Find(int nod)
{
    while(tata[nod]!=nod) nod=tata[nod];
    return nod;
}
int main()
{
    f>>n>>m;
    for(i=1; i<=max(m,n); ++i)
    {
        if(i<=m) f>>v[i].x>>v[i].y>>v[i].c;
        if(i<=n) tata[i]=i;
    }
    sort(v+1,v+m+1,cmp);
    for(i=1; i<=m&&ct<n-1; ++i)
    {
        val1=Find(v[i].x);
        val2=Find(v[i].y);
        if(val1!=val2)
        {
            ct++;
            viz[i]=true;
            s+=v[i].c;
            tata[val1]=val2;
        }
    }
    g<<s<<"\n"<<ct<<"\n";
    for(i=1; i<=m; ++i)
        if(viz[i]==true)
            g<<v[i].x<<" "<<v[i].y<<"\n";
    return 0;
}