#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>

using namespace std;

struct muchie
{
    int in, out, cost;
    bool operator <(const muchie& pt) const
    {
        return this->cost < pt.cost;
    }
};

void citire(int &nr_noduri, int &nr_muchii, vector<muchie> &v)
{
    ifstream f("apm.in");
    muchie nou;
    int i, in, out, cost;
    
    f >> nr_noduri;
    f >> nr_muchii;
    for (i = 1; i <= nr_muchii; i++)
    {
        f >> in >> out >> cost;
        
        nou.in = in;
        nou.out = out;
        nou.cost = cost;
        v.push_back(nou);
    }
}

int find(int vect[], int n)
{
    int nod = n;
    while (vect[nod] != -1)
    {
        if (vect[nod] != -1) nod = vect[nod];
    }
    return nod;
    
}

int main()
{
    ofstream g("apm.out");
    int i=0,nr_nod,nr_muchie, cost=0,x[200000],l=0;
    vector<muchie> v;
    citire(nr_nod, nr_muchie, v);
    int *p = new int[nr_nod];
    for (i = 0; i <= nr_nod; i++)
        p[i] = -1;
    
    sort(v.begin(), v.end());
    for (muchie i : v)
    {
        if (find(p, i.out) != find(p, i.in))
        {
            cost = cost + i.cost;
            p[find(p, i.out)] = i.in;
            //cout << i.in << " " << i.out << " " << i.cost << "\n";
            x[++l] = l;
        }
    }
    g << cost << "\n" << nr_nod - 1<<"\n";
    for (i = 1; i <= nr_nod - 1; i++)
        g << v[x[i]].in << " " << v[x[i]].out << "\n";
    return 0;
}