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

using namespace std;

#define nmax 200200

vector < pair <int, int> > graph[nmax];
int n,m;

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

void read_data() {
    f >> n >> m;
    for( int i = 0; i < m; i++ ) {
        int a, b, c;
        f >> a >> b >> c;
        graph[a].push_back( make_pair(b,c) );
        graph[b].push_back( make_pair(a, c) );

    }
}

void solve() {
    int start = 1;
    priority_queue < pair <int, pair<int, int> > > myheap;

    for( auto x : graph[1]) {
        int cost = x.second * -1;
        int nextNod = x.first;
        myheap.push( make_pair( cost, make_pair(1, nextNod) ) );
    }

    vector <bool> viz( n+1, false);
    viz[start] = true;
    int dadada[nmax];
    int lungime = 0;
    int nrMuchii = 0;
    while( myheap.size() ) {
        pair <int, pair <int, int> > muchie;
        muchie = myheap.top();
        myheap.pop();
        int nextNode = muchie.second.second;
        int node = muchie.second.first;
        if( viz[nextNode] ) continue;
        viz[nextNode] = true;
        dadada[nextNode] = node;
        lungime += muchie.first * -1;
        nrMuchii++;

        for( auto x : graph[nextNode] ) {
            int vecinut = x.first;
            int scumpulet = x.second;
            myheap.push( make_pair( scumpulet * -1, make_pair(nextNode, vecinut) ) );
        }
    }
    g << lungime << "\n";
    g << nrMuchii<<"\n";
    for(int i = 2; i <= n; i++) g << dadada[i] << " " << i << "\n";
 }

int main() {
    read_data();
    solve();
    return 0;
}