#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
vector <int> first, second, cost, map;
vector <pair <int, int> > sol;
int forest[200000];
int group(int i)
{
    if(forest[i] == i)
        return i;
    forest[i] = group(forest[i]);
    return forest[i];
}
bool comp(int i, int j)
{
    return (cost[i] < cost[j]);
}
int main()
{
    ifstream in("apm.in");
    int n, m;
    in >> n >> m;
    for(int i = 0, a, b, c; i < m; ++i)
    {
        in >> a >> b >> c;
        first.push_back(a);
        second.push_back(b);
        cost.push_back(c);
        map.push_back(i);
    }
    in.close();
    sort(map.begin(), map.end(), comp);
    for(int i = 0; i < n; ++i)
        forest[i] = i;
    int min = 0;
    for(int i = 0; i < m; ++i)
    {
        if(group(first[map[i]]) != group(second[map[i]]))
        {
            min += cost[map[i]];
            forest[group(first[map[i]])] = group(second[map[i]]);
            sol.push_back(make_pair(first[map[i]],second[map[i]]));
        }
    }
    ofstream out("apm.out");
    out << min << "\n" << sol.size() << "\n";
    for(int i = 0; i < sol.size(); ++i)
        out << sol[i].second << " " << sol[i].first << "\n";
    out.close();
    return 0;
}