#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
const int maxn = 200005;
vector <pair <int, int> > sol;
int F[maxn];

struct per
{
    pair <int, int> noduri;
    int cost;
};
per muchii[maxn * 2];
int rad(int nod)
{
    return (F[nod] < 0) ? nod : rad(F[nod]);
}

void add(int x, int y)
{
    if(F[x] > F[y])
    {
        F[y] += F[x];
        F[x] = y;
    }
    else
    {
        F[x] += F[y];
        F[y] = x;
    }
}

inline bool cmp(per a, per b)
{
    return a.cost <= b.cost;
}

int main()
{
    int n, m;
    in >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        per p;
        in >> p.noduri.first >> p.noduri.second >> p.cost;
        muchii[i] = p;
    }
    sort(muchii + 1, muchii + m + 1, cmp);
    int total = 0;
    for(int i = 0; i < maxn; i++)
        F[i] = -1;
    for(int i = 1; i <= m; i++)
    {
        int x = muchii[i].noduri.first;
        int y = muchii[i].noduri.second;
        int a = rad(x);
        int b = rad(y);
        if(a != b)
        {
            sol.push_back(make_pair(x, y));
            add(a, b);
            total += muchii[i].cost;
        }
    }
    out << total << "\n" << sol.size() << "\n";
    for(auto it : sol)
        out << it.first << " " << it.second << "\n";
    return 0;
}