#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;
typedef struct {int x, y, cost;}muchie;
void citire(muchie v[], int &n, int &m)
{
    ifstream fin("graf.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, vector <muchie> &x)
{
    int i;
    cost_total = 0;
    k = 0;
    for(i = 0; i <= n; i++)
        viz[i] = i;

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

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

            for(int j = 0; j < n; j++) ///reuniunea
                if(viz[j] == a)
                    viz[j] = a;
        }
    }
}
int main()
{
    muchie v[100];
    vector <muchie> x;
    int n, m, viz[100], k, cost_total;
    citire(v, n, m);
    kruskal(v, n, m, viz, cost_total, k, x);
    ofstream fout("graf.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;
}