#include <bits/stdc++.h>
using namespace std;

const int DMAX = 400001, NMAX = 200001;

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

struct muchie
{
    int x, y, cost;
};
muchie m[DMAX], P[DMAX];

int N, M, T[NMAX], nr, cant;

inline bool cmp(muchie A, muchie B)
{
    return A.cost < B.cost;
}

void init()
{
    int a, b, c;
    f >> N >> M;
    for (int i = 1; i <= M; i++) {
        f >> a >> b >> c;
        m[i].x = a;
        m[i].y = b;
        m[i].cost = c;
    }
}

int Find(int x)
{
    if (T[x] == 0)
        return x;
    else
        return T[x] = Find(T[x]);
}

void Kruskal()
{
    int cx, cy;
    sort (m + 1, m + 1 + M, cmp);
    for (int i = 1; i <= M; i++) {
        cx = Find(m[i].x);
        cy = Find(m[i].y);
        if (cx != cy) {
            T[cx] = cy;
            nr++;
            P[nr] = m[i];
            cant += m[i].cost;
        }
    }
}

void afis()
{
    g << cant << '\n';
    g << nr << '\n';
    for (int i = 1; i <= nr; i++) {
        g << P[i].y << " " << P[i].x << '\n';
    }
}

int main()
{
    init();
    Kruskal();
    afis();
    f.close();
    g.close();
    return 0;
}