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:
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define P pair
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define V vector
#define RE return
#define ALL(a) a.begin(),a.end()
#define MP make_pair
#define PB push_back
#define PF push_front
#define FILL(a,b) memset(a,b,sizeof(a))
using namespace std;
int er[20],p[20][20],sum[40000],dp[20][40000],n; 
V<int> v[40000];
int main(){
	ios::sync_with_stdio(0);
    cin.tie(0);
	int x,y,z,m;
	cin>>n>>m;
	FOR(i,1,m){
		cin>>x>>y>>z;p[x][y]=p[y][x]=z;
	}
	er[0]=1;
	FOR(i,1,n)er[i]=er[i-1]*2;
	FOR(i,1,er[n]-1){
		FOR(j,1,n)if(i&er[j-1])v[i].PB(j);
		sum[i]=sum[i^er[v[i][0]-1]];
		for(int j=1;j<v[i].size();j++){
			sum[i]+=p[v[i][0]][v[i][j]];
		}
	}
	FOR(i,0,er[n]-1)FOR(j,1,n)dp[j][i]=1000000000;
	dp[1][1]=0;
	FOR(mask,1,er[n]-1){
		FOR(i,1,n){
			if(!(mask&er[i-1])||dp[i][mask]>=1000000000)continue;
			FOR(j,1,n){
				if(mask&er[j-1]||!p[i][j])continue;
				dp[j][mask^er[j-1]]=min(dp[j][mask^er[j-1]],dp[i][mask]+sum[mask^er[i-1]^er[j-1]]-sum[mask^er[i-1]]);
			}
			int s=(er[n]-1)^mask,t=s;
			while(t){
				dp[i][mask^t]=min(dp[i][mask^t],dp[i][mask]+sum[mask^er[i-1]^t]-sum[mask^er[i-1]]-sum[t]);
				t=(t-1)&s;
			}
		}
	}
	cout<<dp[n][er[n]-1]<<'\n';
	RE 0;
}