#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define nl '\n'

using namespace std;

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

const int NMAX = 2*1e5+1;

int P[NMAX], sz[NMAX];
int n, m, totalW;
struct edge
{
    int u, v, w;
};
edge x;
vector<edge> edges, apm;

bool cmp(edge &a, edge &b)
{
    return a.w < b.w;
}

int findd(int u)
{
    if (u == P[u])
        return u;
    return P[u] = findd(P[u]);
}

bool sameComp(int u, int v)
{
    u = findd(u);
    v = findd(v);
    return (u == v);
}

void unite(int u, int v)
{
    u = findd(u);
    v = findd(v);
    if (u != v)
    {
        if (sz[u] < sz[v])
            swap(u, v);
        sz[u]+=sz[v];
        P[v] = u;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    fin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        P[i] = i;
        sz[i] = 1;
    }
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        fin >> u >> v >> w;
        edges.push_back({u, v, w});
    }
    sort(edges.begin(), edges.end(), cmp);
    for (int i = 0; i < m; i++)
    {
        x = edges[i];
        if (!sameComp(x.u, x.v))
        {
            unite(x.u, x.v);
            totalW+=x.w;
            apm.push_back(x);
        }
    }
    fout << totalW << nl << n-1 << nl;
    for (int i = 0; i < apm.size(); i++)
        fout << apm[i].u << ' ' << apm[i].v << nl;
    return 0;
}