//created by missever

#include<bits/stdc++.h>
#define MAX 1000000007
using namespace std;
typedef long long LL;
typedef pair<int,int> P;

int f[1 << 15][15],g[1 << 15];
int p[15][15];

void add(int &x,int y) {
    x = max(x,y);
}

int main() {
    int n,m,i,j,k,u,v,w,s = 0;
    scanf("%d%d",&n,&m);
    for(i = 0; i < m; i++) {
        scanf("%d%d%d",&u,&v,&w);
        u--;
        v--;
        p[u][v] = p[v][u] = w;
        s += w;
    }
    memset(f,-1,sizeof(f));
    for(i = 0; i < (1 << n); i++) {
        for(j = 0; j < n; j++) {
            if(!((i >> j) & 1)) continue;
            for(k = j + 1; k < n; k++) {
                if((i >> k) & 1) g[i] += p[j][k];
            }
        }
        if(i & 1) f[i][0] = g[i];
    }
    for(i = 0; i < (1 << n); i++) {
        for(j = 0; j < n; j++) {
            if(f[i][j] != -1) {
                for(k = 0; k < n; k++) {
                    if(((i >> k) & 1) || !p[j][k]) continue;
                    add(f[i | (1 << k)][k],f[i][j] + p[j][k]);
                    u = ((1 << n) - 1) ^ i ^ (1 << k);
                    for(v = u; v; v = (v - 1) & u) add(f[i | (1 << k) | v][k],f[i][j] + p[j][k] + g[v | (1 << k)]);
                }
            }
        }
    }
    printf("%d\n",s - f[(1 << n) - 1][n - 1]);
    return 0;
}
