function Main(input) {
    input = input.trim().split("\n").map(function(x) { return x.split(" ")});
    let lVl = parseInt(input[0][0], 10);
	let lEl = parseInt(input[0][1], 10);
	dp = []; //global
    graph = []; // global
    for (let i = 0; i < lVl; i++){
        graph.push([]);
        for  (let j = 0; j < lVl; j++){
            graph[i][j] = Infinity;
        }
        graph[i][i] = 0;
    }
    for (let i = 0; i < lEl; i++){
        graph[parseInt(input[i + 1][0], 10)][parseInt(input[i + 1][1], 10)] = parseInt(input[i + 1][2], 10);
    }
    for (let i = 0; i < Math.pow(2, lVl); i++){
        dp.push([]);
        for (let j = 0; j < lVl; j++) {
            dp[i][j] = -1;
        }
    }
	dp[0][0] = 0; //start from node0
	dp[1][0] = 0;
	
	for (let i = 1; i < lVl; i++) bitDP(Math.pow(2, lVl) - 1, i);
	let ans = Infinity;
	for (let i = 1; i < lVl; i++){
		ans = Math.min(dp[dp.length - 1][i] + graph[i][0], ans);
	}
	if (ans === Infinity) ans = -1;
	console.log(ans);
}

function bitDP(S, v){
	if (S === 0) return (v === 0) ? 0: Infinity;
	if ((S & (1 << v)) === 0) return Infinity; //S does not include v
	if (dp[S][v] !== -1) return dp[S][v]; //initial value?
	let ret = Infinity;
	for (let i = 0; i <= Math.log2(S); i++){
		if (((S ^ (1 << v)) & (1 << i)) === 0) continue;
		ret = Math.min(ret, bitDP((S ^ (1 << v)), i) + graph[i][v]);
	}
	return dp[S][v] = ret;
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

