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

using namespace std;

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

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


inline int root (int nod)
{
    int R;

    for (R = nod; R != tata[R]; R = tata[R]);
    for (int y; nod != R; y = nod, nod = tata[nod], 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);

    for (int i = 1; i <= M; ++ i)
    {
        int x, y, z;
        scanf ("%d %d %d", &x, &y, &z);

        E.PB ( MKP (z, MKP (x, y)) );
    }

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

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

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

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

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

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

    return 0;
}