#include <bits/stdc++.h>

using namespace std;

const int INF = (1 << 30), NMAX(400005);
using VI  = vector<int>;
using VVI = vector<VI>;
using VB  = vector<bool>;

void BUNA(const string& task = "")
{
    if (!task.empty())
        freopen((task + ".in").c_str(), "r", stdin),
                freopen((task + ".out").c_str(), "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
void PA()
{
    exit(0);
}
int Arb[NMAX], Rank[NMAX];
int findR(int val)
{
    int r = val;
    while(r != Arb[r])
        r = Arb[r];

    while(val != Arb[val])
    {
        int y = Arb[val];
        Arb[val] = r;
        val = y;
    }
    return r;
}

void Unite(int x, int y)
{
    if(Rank[x] > Rank[y])
        Arb[x] = Arb[y];
    else Arb[y] = Arb[x];

    if(Rank[x] == Rank[y])
        Rank[y]++;
}

struct chestie
{
    int x, y, c;
} Muchie[NMAX];

inline bool cmp(chestie a, chestie b)
{
    return a.c < b.c;
}
vector<chestie> rez;

int main()
{
    BUNA("apm");
    int n, m;
    cin >> n >> m;

    for(int i = 1; i <= m; ++i)
        cin >> Muchie[i].x >> Muchie[i].y >> Muchie[i].c;

    sort(Muchie + 1, Muchie + m + 1, cmp);

    for(int i = 1; i <= n; ++i)
        Arb[i] = i;
    int cost = 0;
    int nrM = 0;
    for(int i = 1; i <= m && nrM < n - 1; ++i)
        if(findR(Muchie[i].x) != findR(Muchie[i].y))
        {
            rez.push_back(Muchie[i]);
            cost += Muchie[i].c;
            Unite(findR(Muchie[i].x), findR(Muchie[i].y));
            ++nrM;
        }

    cout << cost << '\n' << nrM << '\n';
    for(auto it: rez)
        cout << it.x << ' ' << it.y << '\n';
    PA();
}