#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

int n, m, total, root[200005], sz[200005], maxi;
struct muchie {
    int a, b, cost;
    inline bool operator < (const muchie &other) const
    {
        return cost > other.cost;
    }
};
priority_queue <muchie> heap;
vector <muchie> ans;

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

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

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        muchie mc;
        fin >> mc.a >> mc.b >> mc.cost;
        heap.push(mc);
    }
    while(!heap.empty())
    {
        muchie mc = heap.top();
        heap.pop();
        int x, y;
        x = find_root(mc.a);
        y = find_root(mc.b);
        if(x == y)
            continue;
        join(x, y);
        total += mc.cost;
        ans.push_back(mc);
    }
    fout << total << '\n' << n - 1 << '\n';
    for(int i = 0; i < (int) ans.size(); i++)
        fout << ans[i].a << ' ' << ans[i].b << '\n';
    return 0;
}