#include <limits.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

#define NONEXISTENT_EDGE -1

typedef struct {
	uint32_t n_vertices;
	int32_t **distances;
	int32_t **dp;
} tsp_info_t;

/***
 *   Check if the bit corresponding to the vertex is set in the given state.
 */
static inline int state_has_vertex(uint32_t state, uint32_t vertex) {
	return vertex ? (state & (1 << (vertex - 1))) : 1;
}

/***
 *   Toggle the bit corresponding to the given vertex in the given state.
 */
static inline uint32_t state_toggle_vertex(uint32_t state, uint32_t vertex) {
	return vertex ? state ^ (1 << (vertex - 1)) : state;
}

/***
 *   Compute the shortest path that contains all the vertices represented by the
 * given state and ends in vertex. If the state doesn't contain the vertex, the
 * result will be infinite.
 *   The result will be stored in p_info->dp[state][vertex] and this is the only
 * value that might be updated from the whole tsp_info_t structure
*/
void tsp_update_distances(tsp_info_t *p_info, uint32_t state, uint32_t vertex)
{
	p_info->dp[state][vertex] = INT_MAX >> 1;
	// Ignore if the current state doesn't contain the given vertex
	if (!state_has_vertex(state, vertex)) return;

	/// Try to update the current distances
	int n = p_info->n_vertices;
	int previous_state = state_toggle_vertex(state, vertex);
	for (int i = 0; i < n; ++i) {
		// Ignore self loops and nonexistent edges
		if (i == vertex || p_info->distances[i][vertex] == NONEXISTENT_EDGE) continue;
		// Ignore if the current state doesn't contain the intermmediate vertex
		if (!state_has_vertex(state, i)) continue;
		// Compute the new candidate value and safe the minimum
		int32_t tmp = p_info->dp[previous_state][i] + p_info->distances[i][vertex];
		if (p_info->dp[state][vertex] > tmp) p_info->dp[state][vertex] = tmp;
	}
}

int main(void)
{
	tsp_info_t info;
	uint32_t n_edges;
	int32_t ans;

	freopen("hamilton.in", "rt", stdin);
	freopen("hamilton.out", "wt", stdout);

	/// Initialize everything and read the data
	scanf("%d %d", &info.n_vertices, &n_edges);
	info.distances = malloc(sizeof(int32_t *) * info.n_vertices);
	for (int i = 0; i < info.n_vertices; ++i) {
		info.distances[i] = malloc(sizeof(int32_t) * info.n_vertices);
		for (int j = 0; j < info.n_vertices; ++j) {
			info.distances[i][j] = NONEXISTENT_EDGE;
		}
	}
	info.dp = malloc(sizeof(int32_t *) * (1 << (info.n_vertices - 1)));
	for (int i = 0; i < (1 << (info.n_vertices - 1)); ++i) {
		info.dp[i] = malloc(sizeof(int32_t) * info.n_vertices);
	}
	for (int i = 0; i < n_edges; ++i) {
		int32_t a, b, d;
		scanf("%d %d %d", &a, &b, &d);
		info.distances[a][b] = d;
	}

	/// Compute the answer
	for (int state = 0; state < (1 << (info.n_vertices - 1)); ++state) {
		info.dp[state][0] = state == 0 ? 0 : INT_MAX >> 1;
		for (int vertex = 1; vertex < info.n_vertices; ++vertex) {
			tsp_update_distances(&info, state, vertex);
		}
	}
	ans = INT_MAX >> 1;
	for (int i = 1; i < info.n_vertices; ++i) {
		if (info.distances[i][0] == NONEXISTENT_EDGE) continue;
		int32_t tmp = info.distances[i][0]
			+ info.dp[(1 << (info.n_vertices - 1)) - 1][i];
		ans = ans < tmp ? ans : tmp;
	}
	printf("%d\n", (1 << (info.n_vertices - 1)) - 1);
	ans = ans == (INT_MAX >> 1) ? -1 : ans;

	/// Print the answer
	printf("%d\n", ans);

	/// Free the used memory
	for (int i = 0; i < info.n_vertices; ++i) {
		free(info.distances[i]);
	}
	free(info.distances);
	for (int i = 0; i < (1 << (info.n_vertices - 1)); ++i) {
		free(info.dp[i]);
	}
	free(info.dp);
	return 0;
}