#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");


const int N = 2e5, M = 4e5;
int n, m, tot;
int t[N+1], rang[N+1];
//vector < pair<int, int> > g[N+1];
vector < pair<int, int> > ans;
vector < pair< int, pair<int, int> > > muchii;


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

void unite(int ra, int rb)
{
    if (rang[ra] > rang[rb])
        t[rb] = ra;
    else
    {
        t[ra] = rb;
        if (rang[ra] == rang[rb])
            rang[rb]++;
    }
}

void kruskal()
{
    // t[] initializat deja cu 0
    for (int i = 1; i <= n; 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);
        int rb = find(b);

        if (ra != rb)
        {
            ans.push_back( make_pair(a, b) );
            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;
        //g[a].push_back( make_pair(b, c) );
        //g[b].push_back( make_pair(a, c) );
        muchii.push_back( make_pair(c, make_pair(a, b)) );
    }


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

    kruskal();

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


    return 0;
}