/*
    Varianta PRIM
*/

#include <bits/stdc++.h>
#define dim 200002
#define inf 1e9 + 1
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

int n, m, x , y, c, sol;
priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > coada;
vector< int > d(dim, inf);     //first -> costul, second -> nodul destinatie
vector<bool> viz(dim);
vector< vector< pair<int, int> > > lista(dim);
vector<int> tata(dim);
vector< pair<int, int> > muchii;

int main() {

    fin >> n >> m;

    for(int i = 0; i < m; i++) {
        fin >> x >> y >> c;
        lista[x].push_back( make_pair(y, c) );
        lista[y].push_back( make_pair(x, c) );
    }

    d[1] = 0;
    coada.push( make_pair(0, 1) );   //plecam si noi ca oamenii din primul nod

    
    for(int i = 0; i < n;) {
        pair<int, int> minimu = coada.top();  //nodul cu cost minim care nu e in apm
        coada.pop();

        
            if( !viz[ minimu.second ] ) {
                int nod = minimu.second;
                int distanta = minimu.first;

                muchii.push_back( make_pair(tata[nod], nod) );

                sol += distanta;
                i++;

                viz[nod] = true;

                for(int j = 0; j < lista[nod].size(); j++) {
                    pair<int, int> vecin = lista[nod][j];   //(nod, cost)
                    if( !viz[ vecin.first ] && d[vecin.first] >  vecin.second ) {
                        tata[vecin.first] = nod;
                        d[vecin.first] =  vecin.second;
                        coada.push( make_pair( d[vecin.first], vecin.first ) );
                    }
                }
            }
        
    }

    fout << sol << '\n' << n - 1 << '\n';

    for(int i = 1; i < muchii.size(); i++) 
        fout << muchii[i].first << " " << muchii[i].second << '\n';

    return 0;
}