#include <bits/stdc++.h>

#define MAX_N 200000
#define MAX_M 400000

using namespace std;

struct EDGE {
    int u, v, c;

    bool operator < (const EDGE &e) const {
        return c < e.c;
    }
};

struct DSU {
    int parent[MAX_N];

    void init( int n ) {
        for ( int i = 0; i < n; i++ )
            parent[i] = i;
    }

    int findParent( int x ) {
        if ( parent[x] != x )
            parent[x] = findParent( parent[x] );
        return parent[x];
    }

    bool same( int x, int y ) {
        return findParent( x ) == findParent( y );
    }

    void unionn( int x, int y ) {
        parent[findParent( y )] = findParent( x );
    }
};

EDGE edge[MAX_M];
DSU arb;
vector <int> ans;

int main() {
    ifstream cin( "apm.in" );
    ofstream cout( "apm.out" );

    int n, m, cost, i;

    cin >> n >> m;
    for ( i = 0; i < m; i++ )
        cin >> edge[i].u >> edge[i].v >> edge[i].c;

    sort( edge, edge + m );

    arb.init( n );

    cost = 0;
    for ( i = 0; i < m; i++ ) {
       if ( !arb.same( edge[i].u, edge[i].v ) ) {
            arb.unionn( edge[i].u, edge[i].v );
            cost += edge[i].c;
            ans.push_back( i );
        }
    }

    cout << cost << "\n" << ans.size() << "\n";
    for ( int e: ans )
        cout << edge[e].v << " " << edge[e].u << "\n";

    return 0;
}