#include <stdio.h>
#include <algorithm>

#define NMAXX 200000
#define MMAXX 400000

using namespace std;

struct Edge {
    int x, y, cost;
};

bool cmpEdge(const Edge& e1, const Edge& e2) {
    return e1.cost < e2.cost;
}

int nrNodes, nrEdges, nrTreeEdges;
int setIndex[NMAXX], treeEdges[MMAXX];
Edge edges[MMAXX];

void init( int n ) {
    int i;

    for ( i = 0; i < n; i++ )
        setIndex[i] = i;
}

int find( int x ) {
    if ( setIndex[x] == x )
        return x;
    return setIndex[x] = find( setIndex[x] );
}

void unite( int x, int y ) {
    int setX, setY;

    setX = find( x );
    setY = find( y );
    if ( setX != setY ) {
        if ( rand() & 1 )
            setIndex[setX] = setY;
        else
            setIndex[setY] = setX;
    }
}

int main() {
    FILE *fin, *fout;
    int i, treeCost;

    fin = fopen( "apm.in", "r" );
    fout = fopen( "apm.out", "w" );

    fscanf( fin, "%d%d", &nrNodes, &nrEdges );
    for ( i = 0; i < nrEdges; i++ ) {
        fscanf( fin, "%d%d%d", &edges[i].x, &edges[i].y, &edges[i].cost );
        edges[i].x--;
        edges[i].y--;
    }

    sort( edges, edges + nrEdges, cmpEdge );

    init( nrNodes );

    treeCost = 0;
    for ( i = 0; i < nrEdges; i++ )
        if ( find( edges[i].x ) != find( edges[i].y ) ) {
            unite( edges[i].x, edges[i].y );
            treeCost += edges[i].cost;
            treeEdges[nrTreeEdges++] = i;
        }

    fprintf( fout, "%d\n%d\n", treeCost, nrTreeEdges );
    for ( i = 0; i < nrTreeEdges; i++ )
        fprintf( fout, "%d %d\n", edges[treeEdges[i]].y + 1, edges[treeEdges[i]].x + 1 );

    fclose( fin );
    fclose( fout );
    return 0;
}