#include <iostream>
#include <cstring>
#include <map>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long

using namespace std;

const int N = 15;

int n, m;
int l[N];
int cost[N][N];
map<int, int> mp;
int ans = 0x3f3f3f3f;

void dfs(int path, int num, int tmp)
{
    if(mp[path])
    {
        if(mp[path] <= tmp) return ;
        else mp[path] = tmp;
    }
    else mp[path] = tmp;
    
    if(num == n)
    {
        ans = min(tmp, ans);
        return ;
    }
    
    if(tmp >= ans) return ;
    //下一个要拓展的点
    for(int i = 1; i <= n; i ++)
    {
        if(l[i]) continue;
        //由谁拓展i
        for(int j = 1; j <= n; j ++)
        {
            if(!l[j] || j == i || cost[i][j] == 0x3f3f3f3f) continue;
            l[i] = l[j] + 1;
            dfs(path + (1 << i), num + 1, tmp + l[j] * cost[j][i]);
            l[i] = 0;
        }
    }
}

signed main()
{
    IOS;
    memset(cost, 0x3f, sizeof cost);
    cin >> n >> m;
    for(int i = 1; i <= m; i ++)
    {
        int a, b, v;
        cin >> a >> b >> v;
        cost[a][b] = cost[b][a] = min(cost[a][b], v);
    }
    for(int i = 1; i <= n; i ++)
    {
        l[i] = 1;
        dfs((1 << i), 1, 0);
        l[i] = 0;
    }
    cout << ans << '\n';
    return 0;
}