#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#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], ApmCost;
vector < pair <int, pair <int, int> > > Edges;
vector < pair <int, int> > sol;


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

    return R;
}


void Unite (int X, int Y)
{
    int Rx = Root (X), Ry = Root (Y);
    tata[Ry] = Rx;
}


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.PB (MKP (X, Y));
        ApmCost += Edges[i].f;
    }

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

    return 0;
}