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

std::ifstream fin ( "apm.in" );
std::ofstream fout ( "apm.out" );

const int NMAX = 200000;
const int MAXM = 2 * NMAX;

int N, M;

struct Edge {
    int x, y, c;

    Edge ( int a, int b, int d ) {
        x = a;
        y = b;
        c = d;
    }

    static bool cmp ( Edge* a, Edge* b ) {
        return a -> c < b -> c;
    }
};

Edge* edges[1 + MAXM];

class Disjoint {
    private : 
        int t[1 + NMAX];
        //int nr[1 + NMAX];
    public :
        Disjoint() {}
        ~Disjoint() {}

        int Root( int x ) {
            if ( t[x] == 0 )
                return x;
            t[x] = Root ( t[x] );
            return t[x];
        }

        void Union ( int x, int y ) {
            int rx = Root ( x );
            int ry = Root ( y );
            t[rx] = ry;
        }

        bool querry ( int x , int y ) {
            return Root(x) == Root(y);
        }
};

std::vector <int> sol;

int main() {

    fin >> N >> M;

    for ( int i = 1; i <= M; ++i ) {
        int x, y, c;
        fin >> x >> y >> c;
        edges[i] = new Edge ( x, y, c );
    }

    std::sort ( edges + 1, edges + M + 1, Edge::cmp );

    int edgeCnt = 0;
    int p = 1;

    Disjoint graph = Disjoint();

    int totalCost = 0;

    while ( p <= M && edgeCnt < N - 1 ) {
        if ( !graph.querry ( edges[p] -> x, edges[p] -> y ) ) {
            ++edgeCnt;
            graph.Union ( edges[p] -> x, edges[p] -> y );
            totalCost += edges[p] -> c;
            sol.push_back ( p );
        }
        ++p;
    }

    fout << totalCost << '\n' << N - 1 << '\n';

    for ( int i = 0; i < sol.size(); ++i )
        fout << edges[sol[i]] -> x << ' ' << edges[sol[i]] -> y << '\n';
    
    graph.~Disjoint();

    fin.close();
    fout.close();

    return 0;
}