Problem: Mole decided to live in an abandoned mine. The structure of the mine is represented by a simple connected undirected graph which consists of N vertices numbered 1 through N and M edges. The i-th edge connects Vertices a_i and b_i, and it costs c_i yen (the currency of Japan) to remove it.

Mole would like to remove some of the edges so that there is exactly one path from Vertex 1 to Vertex N that does not visit the same vertex more than once. Find the minimum budget needed to achieve this.

Constraints

* 2 \leq N \leq 15
* N-1 \leq M \leq N(N-1)/2
* 1 \leq a_i, b_i \leq N
* 1 \leq c_i \leq 10^{6}
* There are neither multiple edges nor self-loops in the given graph.
* The given graph is connected.

Input

Input is given from Standard Input in the following format:


N M
a_1 b_1 c_1
:
a_M b_M c_M


Output

Print the answer.

Examples

Input

4 6
1 2 100
3 1 100
2 4 100
4 3 100
1 4 100
3 2 100


Output

200


Input

2 1
1 2 1


Output

0


Input

15 22
8 13 33418
14 15 55849
7 10 15207
4 6 64328
6 9 86902
15 7 46978
8 14 53526
1 2 8720
14 12 37748
8 3 61543
6 5 32425
4 11 20932
3 12 55123
8 2 45333
9 12 77796
3 9 71922
12 15 70793
2 4 25485
11 6 1436
2 7 81563
7 11 97843
3 1 40491


Output

133677

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

const int N = 15, inf = 0x3f3f3f3f;

int n, m, e[N][1 << N], dp[N][1 << N], sum[1 << N], mask;

#define ctz __builtin_ctz
#define for_bit(i, s) for (int _##i = s, i = ctz(_##i); _##i; i = ctz(_##i = _##i & _##i - 1))

void down(int &x, int y) { x = std::min(x, y); }
int main() {
	std::ios::sync_with_stdio(0), std::cin.tie(0);
	std::cin >> n >> m, mask = ~(-1 << n);
	for (int i = 0, x, y, z; i < m; ++i)
		std::cin >> x >> y >> z, --x, --y, e[x][1 << y] = e[y][1 << x] = z;
	for (int i = 0; i < n; ++i)
		for (int j = 1; j < 1 << n; ++j)
			e[i][j] = e[i][j & -j] + e[i][j & j - 1];
	std::memset(dp, 0x3f, sizeof dp), dp[0][1] = 0;
	for (int s = 0; s <= mask; ++s)
		for_bit(i, s) if (dp[i][s] != inf) {
			int v = dp[i][s], c = mask ^ s;
			if (i != n - 1) for_bit(j, c) if (e[i][1 << j]) down(dp[j][s | 1 << j], v + e[j][s ^ 1 << i]);
			for (int p = c & c - 1; ; p = p - 1 & c) {
				int q = c ^ p; sum[q] = sum[q & q - 1] + e[ctz(q)][s ^ 1 << i];
				if (!p) break;
			}
			for (int p = c; p; p = p - 1 & c) down(dp[i][s | p], v + sum[p]);
		}
	std::cout << dp[n - 1][mask] << '\n';
	return 0;
}