#include <fstream>
#include <algorithm>
#pragma GCC optimize ("O4,Ofast")
#pragma GCC optimize ("unroll-loops")
#define int long long
using namespace std;

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

const int Nmax = 2e5 + 5, Mmax = 4e5 + 5;

struct muchie
{
    int u, v, c;
}edge[Mmax], ans[Mmax];

bool cmp(muchie a, muchie b)
{
    return a.c < b.c;
}

int parent[Nmax], sz[Nmax];
int n;

void init()
{
    for(int i = 0; i <= n; i ++)
    {
        parent[i] = i;
        sz[i] = 1;
    }
}

int findd(int nod)
{
    if(nod == parent[nod])
        return nod;
    return parent[nod] = findd(parent[nod]);
}

void unite(int u, int v)
{
    u = findd(u); v = findd(v);
    if(u == v)
        return;
    if (sz[u] < sz[v])
        swap(u, v);
    sz[u] += sz[v];
    parent[v] = u;
}

signed main()
{
    int m, i, apm = 0, poz = 0;
    cin >> n >> m;
    init();
    for(i = 1; i <= m; i ++)
        cin >> edge[i].u >> edge[i].v >> edge[i].c;
    sort(edge + 1, edge + m + 1, cmp);
    for(i = 1; i <= m; i ++)
        if(findd(edge[i].v) != findd(edge[i].u))
        {
            apm += edge[i].c;
            unite(edge[i].u, edge[i].v);
            ans[++poz] = edge[i];
        }

    cout << apm << '\n';
    cout << poz << '\n';
    for(i = 1; i <= poz; i ++)
        cout << ans[i].u << " " << ans[i].v << '\n';
    return 0;
}