#include <fstream>
#include <iostream>
#include <algorithm>
#define buff_size 400001
using namespace std;
int v[200001],n,m,t,a,b,aux,i,cost=0,lg=0,sol[10000];
char buff[buff_size];
int pos;
struct edge {int x;int y;int c;} tree[400001];
ifstream f("apm.in");
ofstream g("apm.out");

bool cmp(edge a1,edge a2)
{
        return (a1.c<a2.c);
}

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

    for(i=1; i<=m; ++i)   f>>tree[i].x>>tree[i].y>>tree[i].c;
    sort(tree+1,tree+1+m,cmp);
    for(i=1; i<=n; ++i) v[i]=i;



    for(i=1;i<=m;i++)
    {
        a=tree[i].x;
        while(a!=v[a]) aux=v[v[a]],v[a]=aux,a=aux;
        b=tree[i].y;
        while(b!=v[b]) aux=v[v[b]],v[b]=aux,b=aux;

        if(a!=b)
        {
            cost+=tree[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<<tree[sol[i]].x<<' '<<tree[sol[i]].y<<'\n';
    }

}