#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

#define maxN 200010
#define PB push_back
#define MKP make_pair
#define f first
#define s second

int tata[maxN], sol;
vector < pair <int, pair <int, int> > > edges;
vector < pair <int, int> > ans;


inline int root (int X)
{
    int R = X;

    for (R = X; R != tata[R]; R = tata[R]);
    for (int y; X != R; y = X, X = tata[X], tata[y] = R);

    return R;
}


void unite (int x, int y)
{
    int rx = root(x), ry = root (y);
    tata[rx] = ry;
}


int main()
{
    freopen ("apm.in", "r", stdin);
    freopen ("apm.out", "w", stdout);

    int N, M;
    scanf ("%d %d", &N, &M);

    while (M --)
    {
        int x, y, c;
        scanf ("%d %d %d", &x, &y, &c);

        edges.PB ( MKP (c, MKP (x, y)) );
    }

    sort (edges.begin(), edges.end());

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

    for (int i = 0; i < edges.size(); ++ i)
    {
        int x = edges[i].s.f, y = edges[i].s.s;

        if (root (x) == root (y)) continue;

        unite (x, y);
        sol += edges[i].f;
        ans.PB ( MKP (x, y) );
    }

    printf ("%d\n%d\n", sol, ans.size());
    for (int i = 0; i < ans.size(); ++ i) printf ("%d %d\n", ans[i].f, ans[i].s);

    return 0;
}