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

using namespace std;

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

using VI = vector<int>;
using VPI = vector<pair<int, int>>;
using VVPI = vector<VPI>;
using VVI = vector<VI>;
using VTI = vector<tuple<int, int, int>>;

int n, m;
VI dsu;
VVI MST;

int Find(int x)
{
    if (dsu[x] == x)
        return x;

    return dsu[x] = Find(dsu[x]);
}

void Union(int x, int y)
{
    dsu[Find(y)] = Find(x);
}

void DFS(int x, int p)
{
    for (auto y : MST[x])
    {
        if (y == p)
            continue;

        fout << x << ' ' << y << '\n';
        DFS(y, x);
    }
}
int main()
{
    fin >> n >> m;


    int x, y, w;

    VTI valG;
    valG.reserve(m + 1);
    MST = VVI(n + 1);
    dsu = VI(n + 1);

    for (int i = 1; i <= n; ++i)
        dsu[i] = i;

    for (int i = 1; i <= m; ++i)
    {
        fin >> x >> y >> w;
        valG.emplace_back(w, x, y);
    }

    sort(valG.begin(), valG.end());

    int mstmuchii = 0, cost = 0;
    for (auto i : valG)
    {
        if (mstmuchii == n - 1)
            break;

        tie(w, x, y) = i;

        if (Find(x) != Find(y))
        {
            mstmuchii++;
            Union(x, y);
            MST[x].emplace_back(y);
            MST[y].emplace_back(x);
            cost += w;
        }

    }

    fout << cost << '\n' << mstmuchii << '\n';
    DFS(1, 1);
}