#include <fstream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

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

const int NMax = 200000, MMax = 400000;

struct str{int a, b, cost;};

vector <str> V;

vector <pair<int, int> > Sol;

int N, M, TT[NMax + 5], H[NMax + 5], C;

inline bool compare(str A, str B) { return A.cost < B.cost;}

void Read()
{
    fin >> N >> M;

    for(int i = 0, x, y, c; i < M; i++)
    {
        fin >> x >> y >> c;

        V.push_back({x, y, c});
    }
    fin.close();
}

///Disjoint
int Root(int Nod)
{
    while(TT[Nod]) Nod = TT[Nod];

    return Nod;
}

void Unite(int R1, int R2)
{
    if(H[R1] > H[R2])  ///Unesc R2 de R1
        TT[R2] = R1;

    if(H[R1] < H[R2])  ///Unesc R1 de R2
        TT[R1] = R2;

    if(H[R1] == H[R2]) ///Unesc R2 de R1
        TT[R2] = R1, H[R1]++;
}

void Solve()
{
    for(int i = 1; i <= N; i++) H[i] = 1;

    sort(V.begin(), V.end(), compare);

    for(auto X : V)
    {
        int R1 = Root(X.a), R2 = Root(X.b);

        if(R1 != R2)
        {
            Sol.push_back({X.a, X.b});
            C += X.cost;
            Unite(R1, R2);
        }
    }
}

void Print()
{
    fout << C << '\n' << Sol.size() << '\n';

    for(auto X : Sol)
        fout << X.first << " " << X.second << '\n';

    fout.close();
}

int main()
{
    Read();
    Solve();
    Print();

    return 0;
}