#include <fstream>
#include <queue>
#include <functional>
#include <vector>
#define NMAX 200010
#define MMAX 400010

using namespace std;

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

struct muchie
{
    int x, y, c;
    friend bool operator > (muchie a, muchie b);
};

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

int n, m, tata[NMAX], h[NMAX], cmin;
priority_queue<muchie, vector<muchie>, greater<muchie> > H;
vector<muchie> A;

int Find(int x);
void Union(int x, int y);
void citire();
void kruskal();
void afisare();

int main()
{
    citire();
    kruskal();
    afisare();
    return 0;
}

int Find(int x)
{
    int rad = x, y;
    while (tata[rad])
        rad = tata[rad];

    //compresia drumului
    if (rad != x)
    {
        y = tata[x];
        while (y != rad)
        {
            tata[x] = rad;
            x = y;
            y = tata[x];
        }
    }
    return rad;
}
void Union(int x, int y)
{
    int i = Find(x), j = Find(y);
    if (i != j)
    {
        //ponderare
        if (h[i] < h[j])
            tata[i] = j;
        else if (h[j] < h[i])
            tata[j] = i;
        else
        {
            tata[i] = j;
            h[j]++;
        }
    }
}
void citire()
{
    int i;
    muchie aux;
    fin >> n >> m;
    for (i = 0; i < m; i++)
    {
        fin >> aux.x >> aux.y >> aux.c;
        H.push(aux);
    }
}
void kruskal()
{
    int i, j;
    muchie aux;
    while (A.size() < n - 1)
    {
        aux = H.top();
        H.pop();
        i = Find(aux.x);
        j = Find(aux.y);
        if (i != j)
        {
            A.push_back(aux);
            cmin += aux.c;
            Union(i, j);
        }
    }
}
void afisare()
{
    int i;
    fout << cmin << '\n' << A.size() << '\n';
    for (i = 0; i < A.size(); i++)
        fout << A[i].x << ' ' << A[i].y << '\n';
    fout.close();
}