#include <bits/stdc++.h>

using namespace std;
const int N = 18;
int dp[1 << N][N], e[N][N];
vector <pair <int, int>> g[N];

int main()
{
    ifstream cin("hamilton.in");
    ofstream cout("hamilton.out");
    int n, m;
    cin >> n >> m;
    memset(dp, 0x3f, sizeof(dp));
    dp[1][0] = 0;
    for(int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].emplace_back(v, w);
        e[u][v] = w;
    }
    int nn = (1 << n) - 1;
    for(int mask = 1; mask < nn; mask++) {
        for(int cm = mask; cm; cm &= cm - 1) {
            int u = 31 - __builtin_clz(cm & (-cm));
            for(auto [v, w] : g[u]) if(!(mask & (1 << v))) {
                int mv = mask | (1 << v);
                dp[mv][v] = min(dp[mask][u] + w, dp[mv][v]);
            }
        }
    }
    int res = 1e9;
    for(int i = 1; i < n; i++)
        for(int j = 1; j < n; j++) if(j != i && e[i][0])
            res = min(res, dp[nn ^ (1 << i)][j] + e[j][i] + e[i][0]);
    res == 1e9 ? cout << "Nu exista solutie" :
                cout << res;
    return 0;
}