#include <bits/stdc++.h>

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
struct Radu{
    int nod1, nod2, cost;
};
struct pereche{
    int prima, doua;
};
vector <Radu> muchie;
vector <pereche> sol;
int daddy[200001], depth[200001];
int find_daddy( int node ){
    if( node == daddy[node] )
        return node;
    return daddy[node] = find_daddy(daddy[node]);
}
void unire( int node1, int node2 ){
    node1 = find_daddy( node1 );
    node2 = find_daddy( node2 );
    if( depth[node1] > depth[node2] )
        daddy[node2] = node1;
    else if(depth[node1] < depth[node2])
        daddy[node1] = node2;
    else{
        daddy[node2] = node1;
        depth[node1]++;
    }
}
bool cmp( Radu a, Radu b ){
    return a.cost < b.cost;
}
int main()
{
    int n, m, rez, nrmuchii;
    in >> n >> m;
    for( int i = 0; i < m; i++ ){
        int a, b, cost;
        in >> a >> b >> cost;
        muchie.push_back({a, b, cost});
    }
    sort(muchie.begin(), muchie.end(), cmp);
    for( int i = 1; i <= n; i++)
        daddy[i] = i;
    rez = nrmuchii = 0;
    for( int i = 0; i < m; i++ ){
        if( nrmuchii > n-1 )
            break;
        else{
            int nod1 = muchie[i].nod1;
            int nod2 = muchie[i].nod2;
            if( find_daddy(nod1) != find_daddy(nod2) ){
                unire(nod1, nod2);
                nrmuchii++;
                rez += muchie[i].cost;
                sol.push_back({nod1, nod2});
            }
        }
    }
    out << rez << "\n" << n-1 << "\n";
    for( int i = 0; i < sol.size(); i++ )
        out << sol[i].prima << " " << sol[i].doua << "\n";
    return 0;
}