/* Algoritmul lui Prim (determină un rang într-un graf ponderat conex) */
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int n, m;
ifstream fs("apm.in");
ofstream g("apm.out");
typedef struct A
{
    int inc,sf;
    double cost;
} muchie;
vector <A> M;
vector <int> viz;
vector <int> rang;

void init()
{   A muchiee;
    int i;
    fs>>n>>m;
    for(i=0; i <m; i++ )
        M.push_back(muchiee);

    for (i = 0; i < m; i++)
    {
        fs>>M[i].inc;
        fs>>M[i].sf;
        fs>>M[i].cost;
        M[i].inc--;
        M[i].sf--;
    }
    for (i = 0; i < n; i++)
       {

        viz.push_back(0) ;
        rang.push_back(0);

}
}

int costmin()
{
    int rm;
    double q = 1.E15;
    for (int i = 0; i < m; i++)
        if(viz[M[i].inc] !=viz[M[i].sf])
            if(M[i].cost < q)
            {
                rm = i;
                q = M[i].cost;
            }
    return rm;
}

void Prim(int start)
{
    viz[start] = 1;
    for (int i = 0; i < n - 1; i++)
    {
        int rm = costmin();
        rang[i] = rm;
        if(viz[M[rm].inc])
            viz[M[rm].sf] = 1;
        else viz[M[rm].inc] = 1;
    }
}
int main()
{
    double cost_apm = 0;
    int i=1;
    int nr=0;
    init();
    Prim(i - 1);

    for (i = 0; i < n - 1; i++)
    {
        int rm = rang[i];
        cost_apm += M[rm].cost;
        nr++;
    }
    g  << cost_apm << '\n';
    g <<nr<<'\n';
    for (i = 0; i < n - 1; i++)
    {
        int rm = rang[i];
        g << (M[rm].inc + 1) <<" "<< (M[rm].sf + 1)<<'\n';
    }
    fs.close();
    return 0;
}