#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define Nmax 200003
using namespace std;

///-----FISIERE-----
ifstream in("apm.in");
ofstream out("apm.out");

///----TIPURI DE DATE-----
int tata[Nmax], grad[Nmax];
pair <int, pair <int, int> > muchii[Nmax];
pair <int, int> muchieAPM[Nmax];

int FindFather(int nod)
{
    if(tata[nod] == nod)
        return nod;
    tata[nod] = FindFather(tata[nod]);
    return tata[nod];
}
int main()
{
    ///-----CITIRE DATE DIN FISIER----
    int N, M;
    in >> N >> M;
    for(int i = 1; i <= N; i++)
        tata[i] = i;
    int X, Y, C;
    for(int i = 0; i < M; i++)
    {
        in >> X >> Y >> C;
        muchii[i] = make_pair(C, make_pair(X, Y));
    }
    for(int i = 1; i <= N; i++)
		grad[i] = 1;
    sort(muchii + 1, muchii + M +1);
    int nrMuchii = 0;
    int cost = 0;
    for(int i = 1; i <= M; i++)
    {
        int f1 = FindFather(muchii[i].second.first);
        int f2 = FindFather(muchii[i].second.second);
        if(f1 != f2)
        {
            nrMuchii ++;
            cost += muchii[i].first;
            if(grad[f1] > grad[f2])
            {
                tata[f2] = f1;
                grad[f1] += grad[f2];
            }
            else
            {
                tata[f1] = f2;
                grad[f2] += grad[f1];
            }
            muchieAPM[nrMuchii] = make_pair(muchii[i].second.first, muchii[i].second.second);
    }
    }
    out << cost << endl;
    out << nrMuchii << endl;
    for(int i = 1; i <= nrMuchii; i++)
    {
        out << muchieAPM[i].first << "  " << muchieAPM[i].second << endl;
    }
    return 0;

}