#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int v[200001],n,m,t,a,b,aux,i,cost,lg,sol[400001];
struct edge{int x;int y;int c;}arb[400001];
bool cmp(edge a,edge b)
{
return (a.c<b.c);
}

int main()
{
    f>>n>>m;

    for(i=1; i<=m; ++i)
    f>>arb[i].x>>arb[i].y>>arb[i].c;
    sort(arb+1,arb+1+m,cmp);
    for(i=1; i<=n; ++i)
    v[i]=i;
    for(i=1;i<=m;i++)
    {
        a=arb[i].x;
        while(a!=v[a])
        {aux=v[v[a]];
        v[a]=aux;
        a=aux;}
        b=arb[i].y;
        while(b!=v[b])
        {aux=v[v[b]];
        v[b]=aux;
        b=aux;}

        if(a!=b)
        {   cost+=arb[i].c;
            sol[++lg]=i;
            v[a]=b;
            if(lg==n-1)   break;
        }
    }

    g<<cost<<'\n'<<lg<<'\n';
    for(i=1;i<n;i++)
    g<<arb[sol[i]].x<<' '<<arb[sol[i]].y<<'\n';
}