#include <iostream>
#include <fstream>
#include <vector>
#include <utility>

using namespace std;

int main(){
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    int nr_noduri;
    int nr_muchii;
    fin >> nr_noduri >> nr_muchii;
    vector < vector < pair <int, int> > > lista_vecini(nr_noduri+1);
    for( int i = 0; i < nr_muchii; i++ ){
        int intrare, iesire, cost;
        fin >> intrare >> iesire >> cost;
        pair < int, int > pereche;
        pereche.first = iesire;
        pereche.second = cost;
        lista_vecini[intrare].push_back(pereche);
        pereche.first = intrare;
        lista_vecini[iesire].push_back(pereche);
    }
    vector < int > Q;
    for( int i = 1; i <= nr_noduri; i++ ){
        Q.push_back(i);
    }
    vector < int > tata(nr_noduri+1,0);
    vector < int > d(nr_noduri+1,9999999);
    int s = 1;
    d[s] = 0;
    while( Q.size() != 0 ){
        int minim = d[0], poz = 0, poz2 = 0;
        for( int i = 0; i < Q.size(); i++ ){
            if( d[Q[i]] < minim ){
                poz = Q[i];
                minim = d[Q[i]];
                poz2 = i;

            }
        }
        Q[poz2] = Q[ Q.size()-1 ];
        Q.pop_back();
        for( int i = 0; i < lista_vecini[poz].size(); i++ ){
            int v = lista_vecini[poz][i].first;
            int w = lista_vecini[poz][i].second;
            int ok = 0;
            for( int k = 0; k < Q.size() && ok == 0; k++ ){
                if( v == Q[k] ) ok = 1;
            }
            if( ok == 1 && w < d[v] ){
                d[v] = w;
                tata[v] = poz;
            }
        }
    }
    int s1 = 0;
    for( int i = 1; i <= nr_noduri; i++ ){
        s1 = s1 + d[i];
    }
    fout << s1 << endl << nr_noduri-1 << endl;
    for( int i = 2; i <= nr_noduri; i++ ){
        fout << i << " " << tata[i] << endl;
    }
}