#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int maxn = 200005;
const int inf = 0x3f3f3f3f;
typedef int Heap;
Heap H[2 * maxn + 100];
int VEC[maxn], ans, V[maxn], POZ[maxn];
int N, M, L;
vector < pair <int, int> > G[maxn], ARB;

int Father(int k)
{
	return (k >> 1);
}

int Left_Son(int k)
{
	return (k << 1);
}

int Right_Son(int k)
{
	return Left_Son(k) + 1;
}

void Insert_in_Apm(int k)
{
	for (int i = 0; i < G[k].size(); ++i)
	{
		int node = G[k][i].first;
		int cost = G[k][i].second;
		V[node] = min(V[node], cost);
		if (V[node] == cost) VEC[node] = k;
	}
}

void Sift(int poz)
{
	while ((poz * 2 <= L && V[H[poz]] > V[H[poz * 2]]) || (poz * 2 + 1 <= L && V[H[poz]] > V[H[poz * 2 + 1]]))
    {
        if (V[H[poz * 2]] < V[H[poz * 2 + 1]] || poz * 2 + 1 > L)
        {
            swap(H[poz],H[poz * 2]);
            swap(POZ[H[poz]],POZ[H[poz * 2]]);
            poz *= 2;
        }
        else
        {
            swap(H[poz],H[poz * 2 + 1]);
            swap(POZ[H[poz]],POZ[H[poz * 2 + 1]]);
            poz = poz * 2 + 1;
        }
    }
}

void Percolate(int poz)
{
	 while(poz > 1 && V[H[poz]] < V[H[poz / 2]])
    {
        swap(H[poz],H[poz / 2]);
        swap(POZ[H[poz]],POZ[H[poz / 2]]);
        poz = poz / 2;
    }
}

void Insert_in_Heap(int k)
{
	++L;
	H[L] = k;
	POZ[k] = L;
	Percolate(L);
}

int Root()
{
	int R = H[1];
	swap(H[1], H[L]);
	swap(POZ[H[1]], POZ[H[L]]);
	--L;
	Sift(1);
	POZ[R] = 0;
	return R;
}

void Update_Heap(int node)
{
	for (int i = 0; i < G[node].size(); ++i)
	{
		int k = G[node][i].first;
		if (POZ[k])
			Percolate(POZ[k]);
	}
}

int main()
{
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= M; ++i)
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		G[a].push_back(make_pair(b, c));
		G[b].push_back(make_pair(a, c));
	}
	for (int i = 1; i <= N; ++i)
		V[i] = inf;
	V[1] = 0;
	Insert_in_Apm(1);
	for (int i = 2; i <= N; ++i)
		Insert_in_Heap(i);
	for (int i = 1; i < N; ++i)
	{
		int R = Root();
		Insert_in_Apm(R);
		ans += V[R];
		ARB.push_back(make_pair(R, VEC[R]));
		Update_Heap(R);
	}
	printf("%d\n", ans);
	printf("%d\n", N - 1);
	for (int i = 0; i < N - 1; ++i)
		printf("%d %d\n", ARB[i].first, ARB[i].second);
	return 0;
}