#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

const int MAX = 200005;
int n, m, x, y, c;
priority_queue < pair < int, pair < int, int > > > PQ;
vector < pair <int, int> > G[MAX];
bool viz[MAX];
int sum, nod, father;
vector < pair < int, int > > sol;

void apm(){

    PQ.push( make_pair(0, make_pair(1, 0)) );
    while(!PQ.empty()){
        pair < int, pair < int, int > > aux;
        aux = PQ.top();
        nod = aux.second.first;
        father = aux.second.second;
        PQ.pop();
        if(!viz[nod]){
            viz[nod] = 1;
            sol.push_back( make_pair(nod, father) );
            ///cout << nod << endl;
            sum += (-aux.first);
            for(auto it: G[nod])
                if(!viz[it.first])
                    PQ.push( make_pair(-it.second, make_pair(it.first, nod)) );
        }
    }
}

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; ++i){
        fin >> x >> y >> c;
        G[x].push_back( make_pair(y, c) );
        G[y].push_back( make_pair(x, c) );
    }

    apm();

    fout << sum << '\n' << n-1 << '\n';
    for(vector < pair < int, int > > :: iterator it = sol.begin() + 1 ; it < sol.end(); ++it){
        fout << it->first << ' ' << it->second << '\n';
    }


    return 0;
}