#include<fstream>
#include<algorithm>
using namespace std;

int const NLIMIT = 200005;
int const MLIMIT = 400005;

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

int N, M, T, K;

struct Edge {
    int X, Y, C;
} Edges[MLIMIT];

int D[NLIMIT], R[NLIMIT];

pair <int, int> P[MLIMIT];

bool Compare(Edge a, Edge b)
{
    return a.C < b.C;
}

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

    for (int i = 0; i < M; i ++)
        fin >> Edges[i].X >> Edges[i].Y >> Edges[i].C;

    sort(Edges, Edges + M, Compare);

    for (int i = 1; i <= N; i ++)
    {
        D[i] = i;
        R[i] = 1;
    }
}

int Find(int Node)
{
    while (D[Node] != Node)
        Node = D[Node];

    return Node;
}

void Union(int X, int Y)
{
    if (R[X] > R[Y])
        D[Y] = X;
    else if (R[X] < R[Y])
        D[X] = Y;
    else
    {
        D[X] = Y;
        R[Y] ++;
    }
}

void Solve()
{
    for (int i = 0; i < M; i ++)
    {
        int D_X = Find(Edges[i].X), D_Y = Find(Edges[i].Y);

        if (D_X != D_Y)
        {
            Union(D_X, D_Y);
            K ++;
            P[K].first = Edges[i].X;
            P[K].second = Edges[i].Y;
            T += Edges[i].C;
        }
    }
}

void write()
{
    fout << T << "\n" << K << "\n";
    for (int i = 1; i <= K; i ++)
        fout << P[i].first << " " << P[i].second << "\n";
}

int main()
{
    read();
    Solve();
    write();
    return 0;
}