#include <iostream>
#include <fstream>
#include <algorithm>
#define N 200004
using namespace std;

ifstream f("apm.in");
ofstream fout("apm.out");

struct muchie
{
    int x, y, c;
}G[N];

int r[N], rang[N], sol[N];

void citire(int m)
{
    int i=1;
    while(i<=m)
    {
        f >> G[i].x >> G[i].y >> G[i].c;
        i++;
    }
}

bool cond(muchie x, muchie y)
{
    return (x.c<y.c);
}

int root(int x)
{
    while(r[x])
        x=r[x];
    return x;
}
int Kruskal(int m, int n, int &muchii)
{
    int i, Rx, Ry, cost=0;
    for(i=1; i<=n; i++)
        rang[i]=1;
    for(i=1; i<=m && muchii<n-1; i++)
    {
        Rx=root(G[i].x);
        Ry=root(G[i].y);
        if(Rx!=Ry)
        {
            cost=cost+G[i].c;
            sol[++muchii]=i;

            if(rang[Rx]>rang[Ry])
            {
                rang[Rx]=rang[Ry]+rang[Rx];
                r[Ry]=Rx;
            }
            else
            {
                rang[Ry]=rang[Ry]+rang[Rx];
                r[Rx]=Ry;
            }
        }
    }
    return cost;
}
int main()
{
    int n, m, i, muchii=0;
    f >> n >> m;
    citire(m);
    sort(G+1, G+1+m, cond);
    fout << Kruskal(m, n, muchii) << endl;
    fout << muchii << endl;
    for(i=1; i<=muchii; i++)
        fout << G[i].x << " " << G[i].y << " " << endl;

    return 0;
}