#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;
}
*/

int n, m;
vector <pii> adj[NMAX / 2];
bool inMST[NMAX / 2];
vector <pii> Ans;
int lastCost[NMAX / 2], dad[NMAX / 2];

int main () {
    f >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y, cost;
        f >> x >> y >> cost;
        adj[x].pb ({y, cost});
        adj[y].pb ({x, cost});
    }

    priority_queue < pii,  vector <pii>, greater <pii> > pq;

    for (int i = 1; i <= n; ++i) lastCost[i] = 1 << 30;
    pq.push ({0, 1});
    int ans = 0;
    lastCost[1] = 0;

    while (!pq.empty()) {
        pii p = pq.top();
        pq.pop();
        int cost = p.fi;
        int node = p.se;
        inMST[node] = true;
        for (pii &i : adj[node]) {
            if (inMST[i.fi] || lastCost[i.fi] < i.se) continue;
            ans += i.se;
            if (lastCost[i.fi] != (1 << 30)) ans -= lastCost[i.fi];
            lastCost[i.fi] = i.se;
            pq.push ({i.se, i.fi});
            dad[i.fi] = node;
        }
    }
    g << ans << '\n' << n - 1 << '\n';
    for (int i = 2; i <= n; ++i) {
        g << i << ' ' << dad[i] << '\n';
    }

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