#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

const int N = 200000 + 7;
const int M = 400000 + 7;
const int INF = (int) 1e9;

int n;
int m;
int x[M];
int y[M];
int cost[M];
vector<int> g[N];

int t[N];

int get(int a)
{
    if (t[a] == a)
    {
        return a;
    }
    else
    {
        return t[a] = get(t[a]);
    }
}

void unite(int a, int b)
{
    a = get(a);
    b = get(b);
    t[a] = b;
}

int mn[N];
int who[N];

int main()
{
    freopen ("apm.in", "r", stdin);
    freopen ("apm.out", "w", stdout);

    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> x[i] >> y[i] >> cost[i];
        g[x[i]].push_back(i);
        g[y[i]].push_back(i);
    }
    for (int i = 1; i <= n; i++)
    {
        t[i] = i;
    }
    int ans = 0;
    vector<pair<int, int>> all;
    while (1)
    {
        for (int i = 1; i <= n; i++)
        {
            mn[i] = INF;
        }
        for (int i = 1; i <= n; i++)
        {
            for (auto &it : g[i])
            {
                int j = x[it] ^ y[it] ^ i;
                int c = cost[it];
                if (get(i) != get(j) && c < mn[get(i)])
                {
                    mn[get(i)] = c;
                    who[get(i)] = it;
                }
            }
        }
        int cnt = 0;
        for (int i = 1; i <= n; i++)
        {
            cnt += (t[i] == i);
            if (get(x[who[i]]) != get(y[who[i]]) && t[i] == i && mn[i] < INF)
            {
                int it = who[i];
                ans += cost[it];
                mn[y[it]] = INF;
                all.push_back({x[it], y[it]});
                unite(x[it], y[it]);
            }
        }
        if (cnt == 1)
        {
            break;
        }
    }
    cout << ans << "\n";
    cout << (int) all.size() << "\n";
    for (auto &it : all)
    {
        cout << it.first << " " << it.second << "\n";
    }
}