#include <bits/stdc++.h>
#define MOD 666013
using namespace std;
///aproapeperm
ifstream fin("apm.in");
ofstream fout("apm.out");

int n, m;
int t[200005];
vector<tuple<int, int, int>> v;
vector<pair<int, int>> sol;

void Union(int x, int y)
{
    t[y] = x;
}
int FindRoot(int x)
{
    int y, rad = x;
    while (t[rad] != 0)
        rad = t[rad];
    while (x != rad)
    {
        y = t[x];
        t[x] = rad;
        x = y;
    }
    return rad;
}
int main()
{
    int x, y, c, costTotal;
    fin >> n >> m;
    while (m--)
    {
        fin >> x >> y >> c;
        v.push_back(make_tuple(c, x, y));
    }
    costTotal = 0;
    sort (v.begin(), v.end());
    for (tuple<int, int, int> w : v)
    {
        x = get<1>(w); y = get<2>(w); c = get<0>(w);
        x = FindRoot(x); y = FindRoot(y);
        if (x != y)
        {
            costTotal += c;
            Union(x, y);
            sol.push_back({get<1>(w), get<2>(w)});
        }
    }
    fout << costTotal << "\n" << sol.size() << "\n";
    for (auto w : sol)
        fout << w.first << " " << w.second << "\n";
    return 0;
}