#include<bits/stdc++.h>
using namespace std;
const int maxn=100010,mod=998244353;
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline int read(){
	int x=0,f=0;char ch=getchar();
	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
	return f?-x:x;
}
int n,m,lim,wsum,e[15][15],f[1<<15][15],tot[1<<15];
inline void chkmax(int &x,int y){if(x<y) x=y;}
int main(){
	n=read();m=read();lim=1<<n;
	FOR(i,1,m){
		int u=read()-1,v=read()-1;
		wsum+=e[u][v]=e[v][u]=read();
	}
	FOR(i,0,lim-1) FOR(j,0,n-1) if((i>>j)&1) FOR(k,j+1,n-1) if((i>>k)&1) tot[i]+=e[j][k];
	MEM(f,~0x3f);
	f[1][0]=0;
	FOR(i,1,lim-1) FOR(j,0,n-1) if((i>>j)&1){
		FOR(k,0,n-1) if(!((i>>k)&1) && e[j][k]) chkmax(f[i|(1<<k)][k],f[i][j]+e[j][k]);
		int re=(lim-1)^i;
		for(int k=re;k;k=((k-1)&re)) chkmax(f[i|k][j],f[i][j]+tot[k|(1<<j)]);
	}
	printf("%d\n",wsum-f[lim-1][n-1]);
}
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;
typedef long long ll;

int N, M;
int a[300], b[300], c[300];

int g[15][15];

ll dp[1<<15][15];
const ll INF = 1e+12;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(10) << fixed;
    cin >> N >> M;
    int sum = 0;
    for(int i = 0; i < M; i++) {
        cin >> a[i] >> b[i] >> c[i];
        a[i]--; b[i]--;
        g[a[i]][b[i]] = c[i];
        g[b[i]][a[i]] = c[i];
        sum += c[i];
    }
    int fin = (1<<N)-1;
    for(int i = 1; i < (1<<N); i++){
        if(i%2 == 0) continue;
        for(int j = 0; j < N; j++){
            if(!(i&(1<<j))) continue;
            for(int k = j+1; k < N; k++){
                if(!(i&(1<<k))) continue;
                dp[i][0] += g[j][k];
            }
        }
    }
    for(int i = 1; i < (1<<N); i++){
        for(int j = 0; j < N; j++){
            if(i == 1 && j == 0) continue;
            if(dp[i][j] == 0) dp[i][j] = -INF;        
        }
    }
    for(int i = 1; i < (1<<N); i++){
        if(i%2 == 0) continue;
        if(i&(1<<(N-1))) continue;
        for(int j = (i+1)|i; j < (1<<N); j = (j+1)|i){
            int rem = j-i;
            ll sum_rem = 0;
            for(int k = 0; k < N; k++){
                for(int l = k+1; l < N; l++){
                    if((rem&(1<<k)) && (rem&(1<<l))) sum_rem += g[k][l];
                }
            }
            // cout << i << '-' << j << ' ' << rem << ' ' << sum_rem << endl;
            if(j&(1<<(N-1))){
                // N-1に行く
                for(int k = 0; k < N; k++){
                    if(!(i&(1<<k))) continue;
                    if(g[k][N-1] == 0) {}
                    else{
                        // if(i == 7) cout << i << "at"<< k << "dp" << dp[i][k] << '-' << j << endl;
                        dp[j][N-1] = max(dp[j][N-1], dp[i][k]+sum_rem+g[k][N-1]);
                    }
                }
            }else{
                // k -> l
                for(int k = 0; k < N; k++){
                    if(!(i&(1<<k))) continue;
                    for(int l = 0; l < N; l++){
                        if(!(rem&(1<<l))) continue;
                        if(g[k][l] == 0) {}
                        else{
                            dp[j][l] = max(dp[j][l], dp[i][k]+sum_rem+g[k][l]);
                        }
                    }
                }
            }
        }
    }
    ll g_max = 0;
    for(int i = 0; i < (1<<N); i++){
        g_max = max(g_max, dp[i][N-1]);
        // cout << dp[i][N-1] << endl;
    }
    cout << sum-g_max << endl;
}