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

using namespace std;

const string filename = "apm";
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");

int n, m, root[100005], depth[100005], total;

struct muchie {
    int nod1, nod2, cost;
}lm[400005];

vector <int> ans;

int findroot(int x)
{
    if(root[x] == 0)
        return x;
    return findroot(root[x]);
}

void join(int x, int y)
{
    if(depth[x] == depth[y])
        root[x] = y, depth[y]++;
    if(depth[x] < depth[y])
        root[x] = y;
    if(depth[x] > depth[y])
        root[y] = x;
}

bool cmp(muchie a, muchie b)
{
    return a.cost < b.cost;
}

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
        fin >> lm[i].nod1 >> lm[i].nod2 >> lm[i].cost;
    sort(lm + 1, lm + m + 1, cmp);
    for(int i = 1; i <= m; i++)
    {
        int rx = findroot(lm[i].nod1), ry = findroot(lm[i].nod2);
        if(rx == ry)
            continue;
        total += lm[i].cost;
        ans.push_back(i);
        join(rx, ry);
    }
    fout << total << '\n' << n - 1 << '\n';
    for(int elem : ans)
        fout << lm[elem].nod1 << ' ' << lm[elem].nod2 << '\n';
    return 0;
}