#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define dim 200001
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int n, m;
bool b[dim];
int t[dim];
vector<int> adj[dim];
vector<pair<int, pair<int, int> > > muchii;
vector<pair<int, int> >ans;

void init_array(bool v[], int n, bool val)
{
    for (int i = 0; i < n; i++)
        v[i] = val;
}

int get_root(int nod)
{
    int x = nod, next;

    while (t[x])
        x = t[x];

    //scurtarea arborelui
    while (t[nod])
    {
        next = t[nod];
        t[nod] = x;
        nod = next;
    }

    return x;
}

void print_answer(int cost)
{
    fout << cost << '\n' << ans.size() << '\n';
    for (int i = 0; i < ans.size(); i++)
        fout << ans[i].first << ' ' << ans[i].second << '\n';
}

int main()
{
    int m, x, y, c, cost = 0, noduri = 1;

    fin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        fin >> x >> y >> c;

        adj[x].push_back(y);
        adj[y].push_back(y);
        muchii.push_back(make_pair(c, make_pair(x, y)));
    }

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

    for (int i = 0; i < m && noduri < n; i++)
    {
        int n1 = muchii[i].second.first,
            n2 = muchii[i].second.second,
            root1, root2;

        root1 = get_root(n1);
        root2 = get_root(n2);

        //daca muchia leaga doi arbori diferiti
        if (root1 != root2)
        {
            ans.push_back(make_pair(n1, n2));
            t[root1] = n2;
            cost += muchii[i].first;
            noduri++;
        }
    }

    print_answer(cost);


    return 0;
}