#include <bits/stdc++.h>
#define all(cont) cont.begin(), cont.end()
#define pb push_back
#define fi first
#define se second

using namespace std;

typedef pair <int, int> pii;
typedef vector <int> vi;
typedef long long ll;
typedef unsigned long long ull;

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

const int NMAX = 4e5 + 5;
int n, m;
pair <int, pii> v[NMAX];
pii Ans[NMAX / 2];
int dad[NMAX / 2];

int getDad (int x) {
    return ((dad[x] == x) ? (x) : (dad[x] = getDad (dad[x])));
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
#ifdef LOCAL_DEFINE
	freopen (".in", "r", stdin);
#endif
    f >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y, cost;
        f >> x >> y >> cost;
        v[i] = {cost, {x, y}};
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) dad[i] = i;
    sort (v, v + m);
    int i = 0;
    while (i < m) {
        int dad1 = getDad (v[i].se.fi);
        int dad2 = getDad (v[i].se.se);
        if (dad1 != dad2) {
            ans += v[i].fi;
            Ans[++Ans[0].fi] = v[i].se;

            dad[dad1] = dad2;
        }
        ++i;
    }

    g << ans << '\n' << Ans[0].fi << '\n';
    for (int i = 1; i <= Ans[0].fi; ++i) {
        g << Ans[i].fi << ' ' << Ans[i].se << '\n';
    }

    f.close();
    g.close();
    return 0;
}