#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;
    ifstream f("apm.in");
    ofstream g("apm.out");

struct muchie{
    int x;
    int y;
    int c;
}graf[400005], v[200005];

int t[200005];
int n, m, x, y, sum, q;

int radacina(int x)
{
    if(t[x] == 0)
            return x;
    t[x] = radacina(t[x]);
            return t[x];
}

int reuneste(int x, int y)
{
    t[radacina(y)] = radacina(x);
}

int compara(muchie x, muchie y)
{
    return x.c < y.c;
}

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

    for(int i = 0; i < m; i++)
        f >> graf[i].x >> graf[i].y >> graf[i].c;

    sort(graf, graf+m, compara); //sortare graf dupa cost

    for(int i = 0; i < m && q < n -1; i++)
        if(radacina(graf[i].x) != radacina(graf[i].y)){
            sum += graf[i].c;   //incrementam costul total
            reuneste(graf[i].x, graf[i].y); //reunim cei doi arbori
            v[q++] =  graf[i];  //vizitati
        }

    g << sum << "\n" << q <<"\n";
    for(int i = 0; i < q; i++)
        g << v[i].y << " " << v[i].x << "\n";
    return 0;
}