#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define F first
#define S second
//#define int long long
#define ll long long
//#define int  unsigned long long
#define pb push_back
//#define double long double

using namespace std;
using namespace __gnu_pbds;
typedef  tree< int , null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int mod = 1e9 + 7;
const int N = 17;
int dp[1 << N][N], a[N][N], c[1 << N][N];
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("input.txt", "r", stdin);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        int u, v, c;
        cin >> u >> v >> c;
        u--;
        v--;
        a[u][v] = c;
        a[v][u] = c;
    }
    for (int i = 0; i < (1 << n); i++){
        for (int j = 0; j < n; j++){
            for (int l = 0; l < n; l++){
                if (i & (1 << l)){
                    c[i][j] += a[j][l];
                    //cout << i << " " << j << " " << l << " " << c[i][j] << " " << a[0][3] << endl;
                }
            }
        }
    }
    for (int mask = 0; mask < (1 << n); mask++){
        for (int j = 1; j < n; j++){
            dp[mask][j] = 1e9;
        }
    }
    for (int mask = 0; mask < (1 << n); mask++){
        for (int submask = mask; submask; submask = (submask - 1) & mask){
            int x = 0;
            for (int i = 0; i < n; i++){
                if ((1 << i) & submask){
                    x += c[mask ^ submask][i];
                }
            }
           // cout << "x = " << x << endl;
            for (int i = 0; i < n; i++){
                if (!((1 << i) & (mask ^ submask))) continue;
                for (int j = i + 1; j < n; j++){
                    if (!((1 << j) & submask)) continue;
                    if (a[i][j] != 0)
                    dp[mask][j] = min(dp[mask][j], dp[mask ^ submask][i] + x - a[i][j]);
                }
            }
        }
    }
    cout << dp[(1 << n) - 1][n - 1];
}
