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

using namespace std;

#define nmax 200001

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

struct graf {
    int x, y, cost;
} G[nmax];

int n, m;
int x, y, c;
int T[nmax], NR[nmax];
int aux, rez;
stack < pair<int, int> > s;

bool cmp(graf a, graf b)
{
    return a.cost < b.cost;
}

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

int main()
{

    fi >> n >> m;

    for (int i = 1; i <= m; i++)
        fi >> x >> y >> c,
        G[i].x = x,
        G[i].y = y,
        G[i].cost = c;

    for (int i = 1; i <= n; i++)
        T[i] = i, NR[i] = 1;

    sort(G+1, G+m+1, cmp);

    /*
    for (int i = 1; i <= m; i++)
        cout << G[i].x << " " << G[i].y << " " << G[i].cost << "\n";
    */

    for (int i = 1; i <= m; i++)
    {
        int x = G[i].x;
        int y = G[i].y;

        int rX = root(x);
        int rY = root(y);

        if (rX == rY)
            continue;

        if (NR[rX] >= NR[rY])
        {
            NR[rX] += NR[rY];
            T[rY] = rX;
        }
        else
        {
            NR[rY] += NR[rX];
            T[rX] = rY;
        }

        aux++;
        rez += G[i].cost;
        s.push(make_pair(x, y));

        if (aux == n - 1)
            break;
    }

    fo << rez << "\n";
    fo << aux << "\n";
    for (;s.size();)
    {
        fo << s.top().first << " " << s.top().second << "\n";
        s.pop();
    }

    fi.close();
    fo.close();

    return 0;
}