#include <bits/stdc++.h>
#define int long long
#define cin ci
#define cout co
using namespace std;
ifstream cin("hamilton.in");
ofstream cout("hamilton.out");
const int INF = 1e9;
int n, m;
vector<vector<int>> dist, dp;
void ciclu()
{
    dp[(1 << 0)][0] = 0;
    for(int mask = 0; mask < (1 << n); mask ++)
        if(mask & (1 << 0))
            for(int node = 0; node < n; node ++)
                if(mask & (1 << node))
                    for(int next = 0; next < n; next ++)
                        if(next != node && (mask & (1 << next)))
                            dp[mask][node] = min(dp[mask][node], dp[mask ^ (1 << node)][next] + dist[next][node]);

    int ans = INF;
    for(int node = 1; node < n; node ++)
        ans = min(ans, dp[(1 << n) - 1][node] + dist[node][0]);
    cout << ans;

}
int32_t main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin >> n >> m;
    dist.assign(n + 5, vector<int>(n + 5, INF));
    dp.assign((1 << n), vector<int>(n + 5, INF));
    while(m--)
    {
        int x, y, c;
        cin >> x >> y >> c;
        dist[x][y] = c;
    }
    ciclu();
    return 0;
}