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

using namespace std;

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

#define inf 10500
#define nmax 10500

vector< pair<int, int> > graph[nmax];
int         V   , m, tata[nmax], costuri[nmax], l, heap[2 * nmax + 100], poz[nmax];

void read() {
    f >> V >> m;
    for( int i = 0; i < m; i++) {
        int x, y, z;
        f >> x >> y >> z;
        graph[x].push_back( make_pair(y, z) );
        graph[y].push_back( make_pair(x, z) );
    }
}

void prim() {
    int start = 1;
    vector<int > tata( V+1, -1 );
    vector<int> distanta( V+1, INT_MAX);

    vector<bool>viz(V+1, false);
    priority_queue < pair< int, pair< int, int > > > heap;

    distanta[1] = 0; viz[1] = true;
    for( auto x:graph[1] )
        heap.push( make_pair( -1 * x.second, make_pair(1, x.first) ) );
    int suma = 0;
    while( !heap.empty() ) {
        pair< int, pair< int, int > > min;
        min = heap.top();
        heap.pop();
        
        pair<int, int> muchie = min.second;
        int d = min.first;
        if( !viz[muchie.second] ) {
            tata[muchie.second] = muchie.first;
            viz[muchie.second] = true;
            suma += -1 * d;

            for( auto x : graph[muchie.second]  )
                heap.push( make_pair( -1 * x.second, make_pair( muchie.second, x.first ) ) );
        }
        


    }
    
    g << suma << "\n" << V-1 << "\n";
    for(int i = 2; i <= V; i++)
        g << tata[i] << " " << i << "\n";
}

int main() {
    read();
    prim();
    return 0;
}