//#include <bits/stdc++.h>
#include <vector>
#include <queue>
#include <stdio.h>
#include <stdlib.h>

std::vector< std::pair< int, int > >g[200001];
std::priority_queue< std::pair< std::pair< int, int >, int > >pq;
int slct[200001];
std::vector< std::pair< int, int > >apm[200001];

int main() {
    FILE *fin, *fout;
    int n, m, i, x, y, dxy, s = 0, a, b, c, j;
    fin = fopen( "apm.in", "r" );
    fout = fopen( "apm.out", "w" );
    fscanf( fin, "%d%d", &n, &m );
    for ( i = 0; i < m; i++ ) {
        fscanf( fin, "%d%d%d", &a, &b, &c );
        g[a].push_back( { c, b } );
        g[b].push_back( { c, a } );
    }
    pq.push( { { 0, 1 }, 1 } );
    while ( !pq.empty() ) {
        while ( !pq.empty() && slct[pq.top().second] ) {
            pq.pop();
        }
        if ( !pq.empty() ) {
            x = pq.top().first.second;
            y = pq.top().second;
            dxy = -pq.top().first.first;
            s += dxy;
            apm[x].push_back( { x, y } );
            slct[y] = 1;
            for ( i = 0; i < g[y].size(); i++ ) {
                pq.push( { { -g[y][i].first, y }, g[y][i].second } );
            }
        }
    }
    fprintf( fout, "%d\n%d\n", s, n - 1 );
    for ( j = 1; j < apm[1].size(); j++ )
        fprintf( fout, "%d %d\n", apm[1][j].first, apm[1][j].second );
    for ( i = 2; i <= n; i++ ) {
        for ( j = 0; j < apm[i].size(); j++ )
            fprintf( fout, "%d %d\n", apm[i][j].first, apm[i][j].second );
    }
    fclose( fin );
    fclose( fout );
    return 0;
}