#include <bits/stdc++.h>
#define NMAX 200005
#define MMAX 400005

using namespace std;

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

int n, m, minimum_Cost;
int node_x[NMAX], node_y[NMAX], cost[NMAX], position[NMAX], father[NMAX];
vector <int> nodes;

class cmp
{
    public:
        const bool operator () (int a, int b )
        {
            return cost[a] < cost[b];
        }

};

int parent( int node )
{
    if ( node == father[node] )
        return node;
    father[node] = parent(father[node]);
    return father[node];
}

void unite ( int first_Node, int second_Node )
{
    father[parent(first_Node)] = parent(second_Node);
}

int main()
{
    fin>>n>>m;
    for ( int i = 1; i <= n; ++i )
        father[i] = i;
    for ( int i = 1; i <= m; ++i )
    {
        fin>>node_x[i]>>node_y[i]>>cost[i];
        position[i] = i;
    }
    sort(position+1, position+m+1, cmp());
    for ( int i = 1; i <= m; ++i )
    {
        if ( parent(node_x[position[i]]) != parent(node_y[position[i]]) )
        {
            minimum_Cost += cost[position[i]];
            nodes.push_back(position[i]);
            unite(node_x[position[i]], node_y[position[i]]);
        }
    }
    fout<<minimum_Cost<<'\n'<<nodes.size()<<'\n';
    for ( auto i:nodes )
        fout<<node_x[i]<<" "<<node_y[i]<<'\n';

}