#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <tuple>

using namespace std;

vector <tuple<int, int, int> > muchii;
priority_queue <tuple<int, int, int> > heap;
int tata[200005];
int dist[200005];

int find_father(int x)
{
    if (x == tata[x])
        return x;
                                            //cumva e self explanatory
    return find_father(tata[x]);            //te duci in sus din tata in tata pana la capat

}
void unite(int x, int y)
{
    if (dist[x] > dist[y])
        tata[y] = tata[x];          //se alege arborele mai mare
    else
        tata[x] = tata[y];      //varianta asta pica si daca x=y
    if (dist[x] == dist[y])
        dist[y]++;                      //asa ca se mareste y
}
int kruskal(int N, int M)
{
    int x, y, c, i = 0, cost = 0;
    tuple <int, int, int> tuplu;
    while (i < N - 1)           //n-1 muchii ale arborelui final
    {
        tuplu = heap.top();
        heap.pop();                 //iau cea mai ieftina muchie
        get<0>(tuplu) = -get<0>(tuplu);
        x = get<1>(tuplu);
        y = get<2>(tuplu);
        c = get<0>(tuplu);
        if (find_father(x) != find_father(y))       //verific daca capetele nu fac parte din acelasi arbore
        {
            cost += c;
            muchii.push_back(make_tuple(c, x, y));  //adaug la lista finala de muchii
            i++;
            unite(find_father(x), find_father(y));  //unesc cei doi arbori
        }
    }
    return cost;
}
int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    int i, N, M, x, y, c;
    f >> N >> M;
    for (i = 1; i <= N; i++)
    {
        tata[i] = i;  // fiecare e intr un arbore separat
        dist[i] = 1; // de inaltime 1
    }
    for (i = 1; i <= M; i++)
    {
        f >> x >> y >> c;
        heap.push(make_tuple(-c, x, y)); //sortez toate muchiile
    }
    g << kruskal(N, M) << "\n";
    int lim = muchii.size();
    g << lim << "\n";
    for (i = 0; i < lim; i++)
        g << get<1>(muchii[i]) << " " << get<2>(muchii[i]) <<"\n";
    return 0;
}