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

using namespace std;

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

const int MAXN = 200010;
const int MAXM = 400010;

struct muchie
{
    int a, b, c;
} V[MAXM];

int T[MAXN], Sol[MAXN];

inline bool comp (const muchie &A, const muchie &B)
{
    return A.c < B.c;
}

int Find (const int &node)
{
    if (node == T[node])
        return node;

    return (T[node] = Find (T[node]));
}

int main()
{
    int N, M, i;
    int Tx, Ty;
    int Ans = 0;

    in >> N >> M;
    for (i = 1; i <= M; i ++)
        in >> V[i].a >> V[i].b >> V[i].c;
    sort (V + 1, V + M + 1, comp);

    for (i = 1; i <= N; i ++)
        T[i] = i;

    for (i = 1; i <= M; i ++){
        Tx = Find (V[i].a);
        Ty = Find (V[i].b);

        if (Tx != Ty){
            Ans += V[i].c;
            T[Tx] = Ty;
            Sol[++ Sol[0]] = i;
        }
    }

    out << Ans << "\n" << N - 1 << "\n";
    for (i = 1; i < N; i ++)
        out << V[Sol[i]].a << " " << V[Sol[i]].b << "\n";

    return 0;
}