#include <cstdio>
#include <cstring>

#define MAX 32
#define INF 1 << 30

struct muchie {
	int x, y;
};

muchie M[MAX];
int G[MAX][MAX], C[MAX][MAX], A[MAX][MAX], viz[MAX], used[MAX], Msol[MAX], n, m, N, cst, nr, msol, sol;

void citire (), DFS (int), back (int), afisare ();

int main () {
	
	citire ();
	
	back (1);
	
	afisare ();
	
	return 0;
}

void citire () {
	
	freopen ("apm.in", "r", stdin);
	
	int i, x, y, c;
	
	scanf ("%d %d", &n, &m);
	
	for (i = 1; i <= m; i++) {
		scanf ("%d %d %d", &x, &y, &c);
		G[x][y] = G[y][x] = 1, C[x][y] = c;
		M[i].x = x, M[i].y = y;
	}
	
	sol = INF;
}

void DFS (int nod) {
	
	int i;
	
	viz[nod] = 1, nr++;
	for (i = 1; i <= n; i++) {
		if (A[nod][i] && !viz[i])
			DFS (i);
	}
}

void back (int k) {
	
	int i;
	
	if (N > n - 1)
		return;
	
	if (k == m + 1) {
		if (cst >= sol || N != n - 1)
			return;
		
		nr = 0; memset (viz, 0, sizeof (viz));
		DFS (1);
		if (nr == n) {
			sol = cst;
			for (i = 1, msol = 0; i <= m; i++)
				if (used[i])
					Msol[++msol] = i;
		}
		
		return;
	}
	
	for (i = 0; i <= 1; i++) {
		
		if (i == 0)
			back (k + 1);
		
		if (i == 1) {
			N++;
			cst += C[ M[k].x ][ M[k].y ];
			A[ M[k].x ][ M[k].y ] = A[ M[k].y ][ M[k].x ] = 1, used[k] = 1;
			
			back (k + 1);
			
			N--;
			cst -= C[ M[k].x ][ M[k].y ];
			A[ M[k].x ][ M[k].y ] = A[ M[k].y ][ M[k].x ] = 0, used[k] = 0;
		}
	}
}

void afisare () {
	
	freopen ("apm.out", "w", stdout);

	int i;
	
	printf ("%d\n%d\n", sol, msol);
	
	for (i = 1; i <= msol; i++)
		printf ("%d %d\n", M[ Msol[i] ].x, M[ Msol[i] ].y);
}