#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair
#define N 200005

using namespace std;
int t[N], n, m, x, sol, i, cost, cnt, y;
vector<pair<int, pair<int, int>>>w;
vector < pair<int, int>>vs;

int find(int x)
{
    if(t[x] != x)
        t[x] = find(t[x]);
    return t[x];
}
int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(i = 1; i <= n; i++)
        t[i] = i;
    for(; m; m--)
    {
        scanf("%d%d%d", &x, &y, &cost);
        w.pb(mp(cost, mp(x, y)));
    }
    sort(w.begin(), w.end());
    cnt = n - 1;
    for(auto it : w)
    {
        cost = it.first;
        x = it.second.first;
        y = it.second.second;
        x = find(x);
        y = find(y);
        if(x != y)
        {
            t[x] = y;
            sol += cost;
            vs.pb(mp(x, y));
            cnt--;
        }
        if(!cnt)
            break;
    }
    printf("%d\n%d\n",sol,n-1);
    for(auto it : vs)
        printf("%d %d\n", it.first, it.second);
    return 0;
}