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

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

int n, m;
int t[dim];
bool b[dim];
vector<int> adj[dim];
vector<int> arb[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;
}

void dfs(int nod)
{
    if (b[nod]) return;
    b[nod] = 1;
    for (int i = 0; i < arb[nod].size(); i++)
        dfs(arb[nod][i]);
}

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;

        init_array(b, n + 1, false);
        dfs(n1);
        //daca n2 nu a fost parcurs, inseamna ca muchia adaugata nu formeaza ciclu
        if (!b[n2])
        {
            ans.push_back(make_pair(n1, n2));
            arb[n1].push_back(n2);
            arb[n2].push_back(n1);
            cost += muchii[i].first;
            noduri++;
        }
    }

    print_answer(cost);


    return 0;
}