#include <iostream>
#include <fstream>
#include <algorithm>
#define nMax 200001
#define mMax 400001
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct vertex
{
    int a,b,c; bool tru;
};
vertex muchie[nMax];
int m,n,i,j,v[mMax],r[mMax],cost = 0,nr_muchii=0;

int find_(int x)
{
    if(x == v[x])
        return x;
    return find_(v[x]);
}

void unite_(int x, int y)
{
    int tx=find_(x),ty=find_(y);
    if(r[tx] < r[ty])
        v[tx] = ty;
    else if(r[tx] > r[ty])
        v[ty] = tx;
    else
    {
        v[ty] = tx;
        r[tx]++;
    }
}

bool compara(vertex a, vertex b){return a.c<b.c;}

void kruskal()
{
    sort(&muchie[1], &muchie[m+1], compara);
    for(i=1; i<=n; i++)
        v[i] = i;
    for(i=1; i<=m; i++)
        if(find_(muchie[i].a) != find_(muchie[i].b))
        {
            unite_(muchie[i].a, muchie[i].b);
            cost = cost + muchie[i].c;
            nr_muchii++;
            muchie[i].tru = true;
        }

}

int main()
{

    f>>n>>m;
    for(i=1; i<=m; i++)
        f>>muchie[i].a>>muchie[i].b>>muchie[i].c;
    kruskal();
    g << cost << '\n' << nr_muchii << '\n';
    for(i=1; i<=m; i++)
        if(muchie[i].tru)
            g << muchie[i].a << ' ' << muchie[i].b << '\n';
    return 0;
}