#include <bits/stdc++.h>
#define Nmax 400005
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int N, M, S, K;
struct edge{
   int x, y, c;
};
edge v[Nmax];
bool cmp(edge a, edge b) {
   return a.c < b.c;
}

int father[Nmax], h[Nmax];
int root(int node) {
    int ans;
     while (node) {
        ans = node;
        node = father[node];
     }
    return ans;
}
bool is[Nmax];
int main()
{
    f >> N >> M;
    for (int i = 1; i <= M; ++i)
        f >> v[i].x >> v[i].y >> v[i].c;
    sort(v + 1, v + M + 1, cmp);

    for (int i = 1; i <= M; ++i)
    if (root(v[i].x) != root(v[i].y)) {
         int rx = root(v[i].x), ry = root(v[i].y);
         if (h[rx] >= h[ry]) father[ry] = rx;
         else father[rx] = ry;
         if (h[rx] == h[ry]) ++ h[ry];

         S += v[i].c, ++K;
         is[i] = 1;
    }

    g << S << '\n' << K << '\n';
    for (int i = 1; i <= M; ++i)
        if (is[i]) g << v[i].x << " " << v[i].y << '\n';

    return 0;
}