#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct bongos
{
    int x,y,c;
}v[400005];
int n,m,r1,r2,i,cost, t[200005],h[200005],sol[400005],k;
int comp(bongos a,bongos b)
{
    return a.c<b.c;
}
int rad(int x)
{
    int r,aux;
    r=x;
    while(t[r]!=r)
        r=t[r];
    while(x!=r)
    {
        aux=t[x];
        t[x]=r;
        x=aux;
    }
    return r;
}
void unif(int r1,int r2)
{
    if(h[r1]<h[r2]) t[r1]=r2;
    else t[r2]=r1;
    if(h[r1]==h[r2])
        h[r1]++;
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
        f>>v[i].x>>v[i].y>>v[i].c;
    sort(v+1,v+m+1,comp);
    for(i=1;i<=n;i++)
    {
        t[i]=i;
        h[i]=1;
    }
    for(i=1;i<=m;i++)
    {
        r1=rad(v[i].x);
        r2=rad(v[i].y);
        if(r1!=r2)
        {
            unif(r1,r2);
            cost+=v[i].c;
            sol[++k]=i;
        }
        if(k==n-1)
            break;
    }
    g<<cost<<'\n'<<n-1<<'\n';
    for(i=1;i<=k;i++)
        g<<v[sol[i]].x<<" "<<v[sol[i]].y<<'\n';
    return 0;
}