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

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

const int nmax = 100500;

int frec[nmax], nrAdd, sol[nmax];

vector < pair<int, int> > muchii, graf[nmax];

class cmp{
    public : bool operator() (const pair<int, int> &a, const pair<int, int> &b) {
                return (a.first > b.first);
            };
};

priority_queue < pair<int, int>, vector < pair<int, int> >, cmp > ordine;


int n, m;
int main()
{
    f>>n>>m;

    for(int i = 0, x, y, z; i < m; ++i){
        f>>x>>y>>z;

        graf[x].push_back( make_pair(z, i) );
        graf[y].push_back( make_pair(z, i) );
        muchii.push_back( make_pair(x, y) );
    }

    frec[1] = true;
    nrAdd = 1;

    for( auto node : graf[1] ){
        ordine.push( make_pair(node.first, node.second) );
    }

    int costTot = 0;

    while(nrAdd < n){
        int cost = ordine.top().first, muchie = ordine.top().second;
        int nod1 = muchii[ muchie ].first, nod2 = muchii[ muchie ].second;
        ordine.pop();

        if( !frec[nod1] ){
            frec[nod1] = true;
            ++nrAdd;

            for( auto node : graf[nod1] )
                ordine.push( make_pair(node.first, node.second) );

            sol[ ++sol[0] ] = muchie;
            costTot += cost;
        }

        if( !frec[nod2] ){
            frec[nod2] = true;
            ++nrAdd;

            for( auto node : graf[nod2] )
                ordine.push( make_pair(node.first, node.second) );

            sol[ ++sol[0] ] = muchie;
            costTot += cost;
        }

    }

    g<<costTot<<'\n'<<n - 1<<'\n';

    for(int i = 1; i <= sol[0]; ++i)
        g<<muchii[ sol[i] ].first<<' '<<muchii[ sol[i] ].second<<'\n';
    return 0;
}