#include <bits/stdc++.h>
#define NUM 400005
using namespace std;
vector<pair<int, int>> sol;
struct edge
{
    int st, fin, cost;
};
edge graph[NUM];
int father[NUM];
int rnk[NUM];
int n, m, sum;

int cmp(edge a, edge b)
{
    return a.cost < b.cost;
}

int findCon(int a)
{
    int x, aux;

    for(x = a; x != father[x]; x = father[x]);

    while(a != x)
    {
        aux = father[a];
        father[a] = x;
        a = aux;
    }

    return x;
}

void unite(int a, int b)
{
    if(rnk[a] > rnk[b])
        father[b] = a;
    else
        father[a] = b;

    if(rnk[a] == rnk[b])
        rnk[a]++;
}

int main()
{
	ifstream f("apm.in");
	ofstream g("apm.out");
	f >> n >> m;
	for(int i = 0; i < m; ++i)
        f >> graph[i].st >> graph[i].fin >> graph[i].cost;

    for(int i = 0; i < n; ++i)
    {
        father[i] = i;
        rnk[i] = 1;
    }

    sort(graph, graph + m, cmp);

    for(int i = 0; i < m; ++i)
    {
        if(findCon(graph[i].st) != findCon(graph[i].fin))
        {
            sum += graph[i].cost;
            unite(findCon(graph[i].st), findCon(graph[i].fin));
            sol.push_back({graph[i].st, graph[i].fin});
        }
    }

    g << sum << '\n';
    g << n - 1 << '\n';
    for(int i = 0; i < sol.size(); ++i)
        g << sol[i].first << ' ' << sol[i].second << '\n';

    f.close();
    g.close();
	return 0;
}