#include<bits/stdc++.h>

using namespace std;

const int NMAX = 2e5 + 5;
int n, m, sz[NMAX], tata[NMAX];
vector<pair<int, pair<int, int>>> v;
vector<pair<int, int>> ans;

void unite(int x, int y)
{
    while(x != tata[x])
        x = tata[x];
    while(y != tata[y])
        y = tata[y];

    if(sz[x] > sz[y])
        swap(x, y);

    tata[x] = y;
    sz[y]++;
}

bool check(int x, int y)
{
    while(x != tata[x])
        x = tata[x];
    while(y != tata[y])
        y = tata[y];
    
    if(tata[x] == tata[y])
        return true;
    return false;
}

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

    cin >> n >> m;
    int x, y, c;
    for(int i = 1; i <= m; i++)
    {
        cin >> x >> y >> c;
        v.push_back({c, {x, y}});
    }

    for(int i = 1; i <= n; i++)
    {
        sz[i] = 1;
        tata[i] = i;
    }

    sort(v.begin(), v.end());

    int sum = 0;

    for(int i = 0; i < m; i++)
    {
        if(!check(v[i].second.first, v[i].second.second))
        {
            unite(v[i].second.first, v[i].second.second);
            sum += v[i].first;
            ans.push_back({v[i].second.first, v[i].second.second});
        }
    }

    cout << sum << "\n";
    cout << ans.size() << "\n";
    for(auto u : ans)
        cout << u.first << " " << u.second << "\n";
}