#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;

///complexitate O(m * log(n) + n^2)

typedef struct {int x, y, cost;}muchie;
void citire(muchie v[], int &n, int &m)
{
    ifstream fin("apm.in");
    fin >> n >> m;
    int i;
    for(i = 0; i < m; i++)
        fin >> v[i].x >> v[i].y >> v[i].cost;
    fin.close();
}

int cmp(muchie x, muchie y)
{
    if(x.cost < y.cost)
        return 1;
    return 0;
}

void sortare(muchie *v, int m)
{
    sort(v, v + m , cmp);
}


void kruskal(muchie v[], int n, int m, int viz[], int &cost_total, int &k, muchie x[], int &p)
{
    int i;
    cost_total = 0;
    k = 0;
    for(i = 1; i <= n; i++)
        viz[i] = i;

    ///obligatoriu sortarea
    sortare(v, m);

    for(i = 0; i < m; i++)
    {
        if(viz[v[i].x] != viz[v[i].y])
        {
            x[++p].x = v[i].x;
            x[p].y = v[i].y;
            x[p].cost = v[i].cost;
            k++;
            cost_total += v[i].cost;
            int a = viz[v[i].y];

            for(int j = 1; j <= n; j++) ///reuniunea
                if(viz[j] == a)
                    viz[j] = viz[v[i].x];
            if(k == n - 1)
                break;
        }
    }
}
int main()
{
    muchie v[200001];
    int n, m, viz[200001], k, cost_total;
    citire(v, n, m);
    muchie x[200001];
    int p = 0;
    kruskal(v, n, m, viz, cost_total, k, x, p);
    ofstream fout("apm.out");
    fout << cost_total << "\n";
    fout << k << "\n";
    for(int i = 0; i < k; i++)
        fout << x[i].x << " " << x[i].y << "\n";
    return 0;
}