#include <fstream>
#include <algorithm>
#define MAX 400000
#define NMAX 200000
using namespace std;
ifstream cin ("apm.in");
ofstream cout ("apm.out");
struct ure
{
    int x, y, cost;
};
ure edges[MAX + 10], ans[MAX + 10];
int boss[NMAX + 10], cnt[NMAX + 10];
bool cmp(ure a, ure b)
{
    if (a.cost < b.cost)
        return true;
    return false;
}
int finalBoss(int x)
{
    if (boss[x] == x)
        return x;
    else
        return boss[x] = finalBoss(boss[x]);
}
void join(int x, int y)
{
    int bx = finalBoss(x), by = finalBoss(y);
    if (cnt[bx] < cnt[by])
    {
        boss[bx] = by;
        cnt[by] = cnt[by] + cnt[bx];
    }
    else
    {
        boss[by] = bx;
        cnt[bx] = cnt[bx] + cnt[by];
    }
}
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> edges[i].x >> edges[i].y >> edges[i].cost;
    sort(edges + 1, edges + m + 1, cmp);
    for (int i = 1; i <= n; i++)
    {
        boss[i] = i;
        cnt[i] = 1;
    }
    int minCost = 0, cntEdges = 0;
    for (int i = 1; i <= m; i++)
        if (finalBoss(edges[i].x) != finalBoss(edges[i].y))
        {
            join(edges[i].x, edges[i].y);
            minCost = minCost + edges[i].cost;
            cntEdges++;
            ans[cntEdges].x = edges[i].x;
            ans[cntEdges].y = edges[i].y;
        }
    cout << minCost << '\n' << cntEdges << '\n';
    for (int i = 1; i <= cntEdges; i++)
        cout << ans[i].x << ' ' << ans[i].y << '\n';
    return 0;
}