#include <bits/stdc++.h>
using namespace std;
#define st          first
#define nd          second
#define pb          push_back
#define mkp         make_pair
#define lwbnd		lower_bound
#define upbnd		upper_bound
#define FOR(i,a,b)  for(int i=(a);i<=(b);++i)
#define FORS(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(x)      x.begin(),x.end()
#define SZ(x)       ((int)(x).size())
#define MOD         1000000007 //998244353
#define maxn        200005
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
const int INF=0x3f3f3f3f;

int n, m;
int h[4*maxn], poz[maxn],dep, father[maxn],ans, cost[maxn];
VPII g[maxn];
VPII vans;

void push (int node) {
    int x, y = poz[node];
    while (y != x) {
        x = y;
        if (((x << 1) <= dep) && cost[h[y]] > cost[h[(x << 1)]]) {
            y = (x << 1);
        }
        if ((((x << 1) + 1) <= dep) && cost[h[y]] > cost[h[(x << 1) + 1]]) {
            y = (x << 1) + 1;
        }
        //cout << x << ' '<< y << ' ' << h[y] <<'\n';
        swap(h[x], h[y]);
        swap(poz[h[x]], poz[h[y]]);
    }
}

int read_head() {
    int node = h[1];
    h[1] = h[dep];
    poz[h[1]] = poz[node];
    --dep;
    push(h[1]);
    return node;
}

void repair_heap (int node) {
    while (poz[node] > 1 && cost[h[poz[node]]] < cost[h[poz[node] / 2]]) {
        int p = poz[node];
        swap(poz[h[p]], poz[h[p / 2]]);
        swap(h[p], h[p / 2]);
    }
}

void put_in_heap (int node) {
    h[++dep] = node;
    poz[node] = dep;
    repair_heap(node);
}

void put_in_apm (int node) {
    for(auto it: g[node]) {
        if (cost[it.st] >= it.nd) {
        //cout << it.st << ' ' << it.nd << '\n';
            cost[it.st] = it.nd;
            father[it.st] = node;
            repair_heap(it.st);
        }
    }
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int x, y, c;
    cin >> n >> m;

    FOR(i, 1, m) {
        cin >> x >> y >> c;
        g[x].pb({y,c});
        g[y].pb({x,c});
    }
    FOR (i, 1, n) {
        cost[i] = INF;
    }
    cost[1] = 0;
    put_in_apm(1);
    FOR (i, 2, n) {
        put_in_heap(i);
    }
    FORS (i, 1, n) {
        int node = read_head();
        put_in_apm(node);
        ans += cost[node];
        vans.pb({node, father[node]});
    }
    cout << ans << '\n' << SZ(vans) <<'\n';
    for (auto it: vans) {
        cout << it.first <<' ' << it.second << '\n';
    }

}