#include <fstream>
#include <queue>
#include <vector>
#define NMAX 200004

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

struct Muchie
{
    int x, y, cost;
    friend bool operator >(const Muchie &, const Muchie &);
};

bool operator >(const Muchie & m1, const Muchie & m2)
{
    return m1.cost > m2.cost;
}

priority_queue <Muchie, vector <Muchie>, greater <Muchie> > H;

vector <Muchie> sol;

int tata[NMAX], h[NMAX], n, costmin;

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

int main()
{
    Muchie m;
    citire();
    while (sol.size() < n-1)
    {
        m = H.top();
        H.pop();
        int c1 = Find(m.x);
        int c2 = Find(m.y);
        if (c1 != c2)
        {
            costmin += m.cost;
            sol.push_back(m);
            Union(c1, c2);
        }
    }
    afisare();
    return 0;
}

void citire()
{
    Muchie m;
    int nrm;
    fin >> n >> nrm;
    for (int i = 1; i <= nrm; i++)
    {
        fin >> m.x >> m.y >> m.cost;
        H.push(m);
    }
}

int Find(int x)
{
    int r;
    r = x;
    while (tata[r])
        r = tata[r];
    while (tata[x])
    {
        int r2 = tata[x];
        tata[x] = r;
        x = r2;
    }
    return r;
}

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

void afisare()
{
    fout << costmin << '\n';
    fout << sol.size() << '\n';
    for (int i = 0; i < sol.size(); i++)
    {
        fout << sol[i].x << ' ' << sol[i].y << '\n';
    }
}