#include <bits/stdc++.h>

using namespace std;

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

struct edge
{
    int first_Node, second_Node, cost, position;
};

class cmp
{
    public:
        const bool operator () ( const edge &a, const edge &b )
        {
            return a.cost < b.cost;
        }
};

int n, m, total_Minimum_Cost;

int father[200005];
edge link[400005];

vector <pair<int, int>> pair_of_Nodes;

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

    father[node] = parent(father[node]);
    return father[node];
}

void unite ( int a, int b )
{
    father[parent(a)] = parent(b);
}

int main ()
{
    for ( int i = 1; i <= 200000; ++i )
        father[i] = i;

    fin>>n>>m;

    for ( int i = 1; i <= m; ++i )
    {
        int x, y, c;
        fin>>x>>y>>c;

        link[i] = {x, y, c, i};
    }

    sort(link+1, link+m+1, cmp());

    for ( int i = 1; i <= m; ++i )
    {
        if ( parent(link[i].first_Node) != parent(link[i].second_Node) )
        {
            unite(link[i].first_Node, link[i].second_Node);
            total_Minimum_Cost += link[i].cost;
            pair_of_Nodes.push_back({link[i].first_Node, link[i].second_Node});
        }
    }

    fout<<total_Minimum_Cost<<'\n'<<pair_of_Nodes.size()<<'\n';

    for ( auto x:pair_of_Nodes )
        fout<<x.first<<" "<<x.second<<'\n';
}