#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;


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

const int maxn = 400100;

int GR[maxn], X[maxn], Y[maxn], C[maxn];
int N, M, SOL, ind[maxn];
vector<int> sol;

int grupa(int i)
{
	if (GR[i] == i) return i;
	GR[i] = grupa(GR[i]);
	return GR[i];
}

void reuniune(int i, int j)
{
	GR[grupa(i)] = grupa(j);
}

bool cmpf(int i, int j)
{
	return(C[i] < C[j]);
}

int main()
{
	
	fin >> N >> M;
	for (int i = 1; i <= M; ++i)
	{
		fin>>X[i]>>Y[i]>>C[i];
		ind[i] = i;
	}

	for (int i = 1; i <= N; ++i) GR[i] = i;
	for (int i = 1; i <= N; ++i) GR[i] = i;
	sort(ind + 1, ind + M + 1, cmpf);
	for (int i = 1; i <= M; ++i)
	{
		if (grupa(X[ind[i]]) != grupa(Y[ind[i]])) {
			SOL += C[ind[i]]; reuniune(X[ind[i]], Y[ind[i]]);
			sol.push_back(ind[i]);
		}
	}
	fout<<SOL;
	fout<< N - 1;
	for (int i = 0; i < N - 1; ++i)
		fout<< X[sol[i]]<<Y[sol[i]];
	return 0;
}