#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int NMAX = 400003;
struct muchie
{
    int a, b, cost;
} v[NMAX];

bool cmp(muchie a, muchie b)
{
    return a.cost < b.cost;
}
vector <pair <int, int> > arb;

int t[NMAX];

int root(int val)
{
    if (!t[val])
        return val;
    t[val] = root(t[val]);
    return t[val];
}

bool comun(int x, int y)
{
    int a = root(x);
    int b = root(y);
    return (a == b);
}

void unite(int x, int y)
{
    int a = root(x);
    int b = root(y);
    t[a] = b;
}
int main()
{
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    int n, m, i;
    cin >> n >> m;
    for (i = 1; i <= m; i++)
        cin >> v[i].a >> v[i].b >> v[i].cost;
    sort(v + 1, v + m + 1, cmp);
    int ans = 0;
    for (i = 1; i <= m; i++)
        if (!comun(v[i].a, v[i].b))
        {
            unite(v[i].a, v[i].b);
            arb.push_back({v[i].a, v[i].b});
            ans += v[i].cost;
        }
    cout << ans << "\n" << arb.size() << "\n";
    for (i = 0; i < arb.size(); i++)
        cout << arb[i].first << " " << arb[i].second << "\n";
}