#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


const int N = 2e5;
int n, m, cost_tot;
int t[N+1], rang[N+1];
vector < pair< int, pair<int, int> > > muchii;
vector < pair<int, int> > ans;


int find(int x)
{
    if (t[x] == x)
        return x;
    t[x] = find(t[x]);
    return t[x];
}

void unite(int x, int y)
{
    int rx = find(x), ry = find(y);
    if (rang[x] <= rang[y])
        t[rx] = ry;
    else
        t[ry] = rx;
    
    if (rang[rx] == rang[ry])
        rang[ry]++;
}

void kruskal()
{
    for (int i = 1; i <= n; i++)
    {
        t[i] = i;
        rang[i] = 1;
    }

    for (vector < pair< int, pair<int, int> > > :: iterator it = muchii.begin(); it != muchii.end(); it++)
    {
        int cost = it->first;
        int a = it->second.first;
        int b = it->second.second;
        int ra = find(a), rb = find(b);
        if (ra != rb)
        {
            ans.push_back( it->second );
            cost_tot += cost;
            unite(ra, rb);
        }
    }
}


int main()
{
    cin >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        muchii.push_back( make_pair( c, make_pair(a, b) ) );
    }


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

    kruskal();

    cout << cost_tot << '\n';
    cout << ans.size() << '\n';
    for (auto pereche : ans)
        cout << pereche.first << ' ' << pereche.second << '\n';


    return 0;
}