#include <cstdio>
#include <vector>
#include <algorithm>
#define NMAX 200000
using namespace std;

struct edge
{
    int x, y, cost;
} v[NMAX + 1];

vector <int> sol;
int dad[NMAX + 1];

int find_daddy(int a)
{
	// dad[i] = tatal lui i
	if (dad[a] == a)
		return a;
	return dad[a] = find_daddy(dad[a]);
}


inline void join(int a, int b)
{
	int rx, ry;
	rx = find_daddy(a);
	ry = find_daddy(b);
	dad[ry] = rx;
}

int check(int a, int b)
{
    int t1 = find_daddy(a);
    int t2 = find_daddy(b);
    if (t1 != t2)
        return 1;
    return 0;
}

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

int main(){
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    int n, m, i, cost;

    scanf("%d%d", &n, &m);
    for (i = 1; i <= m; i++)
        scanf("%d%d%d", &v[i].x, &v[i].y, &v[i].cost);
    sort(v + 1, v + m + 1, cmp);

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

    cost = 0;
    for (i = 1; sol.size() < n - 1; i++)
    {
        if (check(v[i].x, v[i].y))
		{
			sol.push_back(i);
			cost = cost + v[i].cost;
			join(v[i].x, v[i].y);
		}
    }

    printf("%d\n%d\n", cost, n - 1);
    for (auto i: sol)
        printf("%d %d\n", v[i].x, v[i].y);

    return 0;
}