#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

const int NMAX = 400000;

struct muchie
{
    int u, v, c, pus; //poti c short int
};

muchie x[NMAX + 5];
int t[200005], h[200005];

int varf(int x)
{
    while(t[x] != x)
        x = t[x];//ii aflam tatal lui
    return x;
}

void unire(int x, int y)
{
    if(h[x] > h[y])
        t[y] = x; //tatal lui y devine x
    else
    {
        if(h[x] < h[y])
            t[x] = y; //tatal lui x devine y
        else //egale
        {
            t[y] = x;
            ++h[x];
        }
    }
}//unim doi arbori

bool cmp(muchie a, muchie b)
{
    return a.c<b.c;
}
int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    int n, m, cost, i;
    fin>>n>>m;
    for(i = 1; i <= n; ++i)
        t[i] = i, h[i] = 1;//initial fiecare nod are distanta de la el la varf de 1 si tatal el insusi
    for(i = 1; i <= m; ++i)
        fin>>x[i].u>>x[i].v>>x[i].c; // citesc muchiile si costurile
    cost = 0; // costul total
    sort(x + 1, x + m + 1, cmp); //sortez muchiile in functie de cost
    int rx, ry, ms;
    for(ms = 0, i = 1; ms < n-1; ++i) //&& i <= m; ++i)//care se intampla prima, 1 punem toate cele n-1 muchii necesare arborelui, 2 terminam cele m muchii(in caz ca graful initial nu e conex)
    {
        rx = varf(x[i].u);
        ry = varf(x[i].v);
        if(rx != ry)
        {
            unire(rx, ry); // unim cele doua noduri
            x[i].pus = 1; //am pus muchia
            cost = cost + x[i].c; // actualizam costul
            ++ms;//ms este numarul maxim de muchii pe care le poate avea arborele
        }
    }
    fout<<cost<<'\n';
    fout<<ms<<'\n';
    for(i = 1; i <= m; ++i)
    {
        if(x[i].pus)//daca muchia a fost pusa in apm
            fout<<x[i].u<<' '<<x[i].v<<'\n';
    }
    return 0;
}