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

using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

struct specif_muchie {
    int x, y;
    int cost;
};

struct detect_ciclu {
    vector<int> parinte, rang;
    detect_ciclu(int n=0)
    {
        init(n);
    }
    void init(int n)    //fiecare nod e propriul sau parinte
    {
        parinte.resize(n+1);
        rang.assign(n+1, 0);
        for (int i = 1; i <= n; ++i)
            parinte[i] = i;
    }
    int find(int x)    //reprezentantul comp conexe
    {
        if (parinte[x] == x)
            return x;
        return parinte[x] = find(parinte[x]);
    }
    bool unite(int a, int b)    //unesc cele 2 comp conexe daca sunt diferite
    {
        a = find(a);
        b = find(b);
        if (a == b)
            return false;
        if (rang[a] < rang[b])
            swap(a,b);
        parinte[b] = a;
        if (rang[a] == rang[b])
            rang[a]++;
        return true;
    }
};

int main()
{
    int N, M, x, y, cost;
    in >> N >> M;
    vector<specif_muchie> muchii;
    muchii.reserve(M);
    for (int i = 0; i < M; i++)
    {
        in >> x >> y >> cost;
        muchii.push_back({x,y,cost});
    }
    //sortez cresc muchiile dupa cost - daca au acelasi cost, sort dupa capete
    sort(muchii.begin(), muchii.end(), [](const specif_muchie &A, const specif_muchie &B){
        if (A.cost != B.cost)
            return A.cost < B.cost;
        if (A.x != B.x)
            return A.x < B.x;
        return A.y < B.y;
    });

    //Kruskal adauga muchiile in ord de cost min
    detect_ciclu dsu(N);
    long long total = 0;
    vector<pair<int,int>> p_alese;
    p_alese.reserve(N-1);
    for (const specif_muchie &e : muchii)  //parcurg toate muchiile
    {
        if ((int)p_alese.size() == N-1)
            break;
        if (dsu.unite(e.x, e.y))
        {
            p_alese.emplace_back(e.x, e.y);
            total += e.cost;
        }
    }

    // verific daca am APM (in cerinta am ca graful e conex)
//    if ((int)chosen.size() != N-1)
//    {
//        out << "Nu am arbore de acoperire minim";
//        return 0;
//    }

    out << total << "\n";
    out << (int)p_alese.size() << "\n";
    for (auto &pereche : p_alese)
        out << pereche.second << " " << pereche.first <<"\n";

    in.close();
    out.close();
    return 0;
}