#include <bits/stdc++.h>

using namespace std;

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

using ll = long long;
using pii = pair<int, int>;

const int NMAX = 1e5 + 5;
const int INF = 0x3f3f3f3f;

int n, m, MSTcost, root[NMAX];
vector<pair<int, pair<int, int>>> edges(NMAX);
vector<pii> MST;

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

void Kruskal()
{
    sort(edges.begin(), edges.end());

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

    for (auto e : edges)
    {
        int x, y, wt;
        wt = e.first;
        tie(x, y) = e.second;
        if (getRoot(x) != getRoot(y))
        {
            root[x] = root[y];
            MST.push_back({x, y});
            MSTcost += wt;
            if (MST.size()==n-1)
                return;
        }
    }
}

void read()
{
    in >> n >> m;
    int x, y, wt;
    for (int i = 1; i <= m; i++)
        in >> x >> y >> wt, edges.push_back({wt, {x, y}});
}

void solve()
{
    Kruskal();
    out << MSTcost << '\n';
    out << MST.size() << '\n';
    for (auto e : MST)
        out << e.first << ' ' << e.second << '\n';
}

int main()
{
    read();
    solve();

    return 0;
}