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"
  
using namespace std;

int main(){
  int N,M;
  cin>>N>>M;
  vector<vector<int>>edge(N,vector<int>(N));
  for(int i=0;i<M;i++){
    int a,b,c;
    cin>>a>>b>>c;
    a--;
    b--;
    edge[a][b]=c;
    edge[b][a]=c;
  }
  vector<int>box(1<<N);
  for(int i=0;i<1<<N;i++){
    for(int j=0;j<N;j++){
      if((i>>j)&1){
      	for(int k=j+1;k<N;k++){
          if((i>>k)&1)box[i]+=edge[j][k];
        }
      }
    }
  }
  vector<vector<int>>dp(1<<N,vector<int>(N,-1e9));
  for(int i=1;i<1<<N;i+=2)dp[i][0]=box[i];
  for(int i=1;i<1<<N;i+=2){
    for(int j=0;j<N;j++){
      if(!((i>>j)&1))continue;
      int bag=(1<<N)-1-i;
      int c=bag;
      while(c>0){
        for(int k=1;k<N;k++){
          if(!edge[j][k])continue;
          if((c>>k)&1) dp[i|c][k]=max(dp[i|c][k],dp[i][j]+edge[j][k]+box[c]);
        }
        c--;
        c&=bag;
      }
    }
  }
  int ans=0;
  for(int i=0;i<N;i++){
    for(int j=i+1;j<N;j++)ans+=edge[i][j];
  }
  cout<<ans-dp.back().back()<<endl;
}