#include <iostream>
#include <stdio.h>
#include <algorithm>

using namespace std;

FILE *f=fopen("apm.in","r");
FILE *g=fopen("apm.out","w");

struct vec
{
    int x,y,c;
}v[400001];

int n,m,c[200001],nrm,cost=0,a[400001],mn,mx;

bool cmp(vec i, vec j)
{
    if(i.c<j.c)return 1; else return 0;
}

int Find(int a)
{
    if(a!=c[a])
    return Find(c[a]);
    return c[a];
}

void citire()
{
    int i;
    fscanf(f,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
        fscanf(f,"%d%d%d",&v[i].x,&v[i].y,&v[i].c);
    for(i=1;i<=n;i++)
        c[i]=i;
}

void solve()
{
    int i,j,f1,f2;
    nrm=0;
    for(i=1;nrm<n-1;i++)
        if(Find(c[v[i].x])!=Find(c[v[i].y]))
    {
        cost+=v[i].c;
        a[++nrm]=i;
        f1=Find(c[v[i].x]);
        f2=Find(c[v[i].y]);
        if(f1<f2)
        {
            mn=f1;
            mx=f2;
        } else
        {
            mn=f2;
            mx=f1;
        }
        c[mx]=c[mn];
 /*       for(j=1;j<=n;j++)
            if(c[j]==mx)c[j]=mn;
   */
    }
}

void afisare()
{
    int i;
    fprintf(g,"%d\n",cost);
    fprintf(g,"%d\n",nrm);
    for(i=1;i<=nrm;i++)
        fprintf(g,"%d %d\n",v[a[i]].x,v[a[i]].y);
}

int main()
{
    citire();
    sort(v+1,v+1+m,cmp);
    solve();
    afisare();
    return 0;
}