#include <bits/stdc++.h>

using namespace std;

#ifndef LOCAL
ifstream in("apm.in");
ofstream out("apm.out");
#define cin in
#define cout out
#endif

const int nmax = 2e5 + 7;

int parinte[nmax];
int marime[nmax];

int get_tata(int x)
{
    if(x == parinte[x]) return x;
    else
    {
        int tx = get_tata(parinte[x]);
        parinte[x] = tx;
        return tx;
    }
}

bool Query(int a, int b)
{
    int ta = get_tata(a);
    int tb = get_tata(b);
    if(ta == tb)
    {
        return true;
    }
    else
    {
        return false;
    }
}

void Join(int a, int b)
{
    int ta = get_tata(a);
    int tb = get_tata(b);
    if(ta == tb)
    {
        return;
    }
    if(marime[ta] > marime[tb])
    {
        swap(ta, tb);
    }
    parinte[ta] = tb;
    marime[tb] = marime[ta] + marime[tb];
}

vector<pair<int, pair<int, int>>> muchii;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int u, v, cost;
        cin >> u >> v >> cost;
        muchii.push_back({cost, {u, v}});
    }
    sort(muchii.begin(), muchii.end());
    for (int i = 1; i <= n; i++)
    {
        parinte[i] = i;
        marime[i] = 1;
    }
    int sum = 0;
    vector<pair<int, int>> alese;
    for(auto muchie : muchii)
    {
        int cost = muchie.first;
        int x = muchie.second.first, y = muchie.second.second;
        if(!Query(x, y))
        {
            sum += cost;
            alese.push_back({x, y});
            Join(x, y);
        }
    }
    cout << sum << '\n';
    cout << alese.size() << '\n';
    for(auto muchie : alese)
    {
        cout << muchie.first << ' ' << muchie.second << '\n';
    }
}