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

using namespace std;

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

struct nod
{
    int x, y, cost;
} Graf[400010];

int T[200010];
int Sol[200010];

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

int find (int nod)
{
    if (nod == T[nod])
        return nod;

    return (T[nod] = find (T[nod]));
}

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

    in >> N >> M;

    for (i = 1; i <= M; i ++)
        in >> Graf[i].x >> Graf[i].y >> Graf[i].cost;

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

    sort (Graf + 1, Graf + M + 1, comp);

    for (i = 1; i <= M; i ++){
        Tx = find (Graf[i].x);
        Ty = find (Graf[i].y);

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

    out << Ans << "\n" << Sol[0] << "\n";

    for (i = 1; i <= Sol[0]; i ++)
        out << Graf[Sol[i]].x << " " << Graf[Sol[i]].y << "\n";

    return 0;
}