#include <fstream>
#include <queue>
#include <functional>

using namespace std;

ifstream fin("kruskal.in");
ofstream fout("kruskal.out");

struct muchie
{
    int x, y, c;

    friend bool operator > (muchie a, muchie b)
    {
        return a.c > b.c;
    }
};

int n, m, cost, tata[200005], h[200005];
muchie aux, v[400005];
vector<muchie> sol;

int Find(int x);
void Union(int x, int y);

int main()
{
    int i, ii, jj;

    fin >> n >> m;
    for (i=0;i<m;i++)
        fin >> v[i].x >> v[i].y >> v[i].c;
    priority_queue<muchie, vector<muchie>, greater<muchie> > H(v, v + m);
    while (sol.size() < n-1)
    {
        aux = H.top();
        H.pop();
        ii = Find(aux.x);
        jj = Find(aux.y);
        if (ii != jj)
        {
            Union(ii,jj);
            cost+=aux.c;
            sol.push_back(aux);
        }
    }
    fout << cost << '\n' << n-1 << '\n';
    for (i=0;i<n-1;i++)
        fout << sol[i].x << ' ' << sol[i].y << '\n';
    fout << '\n';
    return 0;
}

int Find(int x)
{
    int rad=x, aux;

    while (tata[rad])
        rad = tata[rad];
    if (x == rad)
        return x;
    while (tata[x] != rad)
    {
        aux = tata[x];
        tata[x] = rad;
        x = aux;
    }
    return rad;
}

void Union(int x, int y)
{
    int i, j;

    i = Find(x);
    j = Find(y);
    if (h[i] > h[j])
        tata[j] = i;
    else if (h[i] < h[j])
        tata[i] = j;
    else
    {
        tata[i] = j;
        h[j]++;
    }
}