#include <bits/stdc++.h>

using namespace std;
vector<vector<int>> adj;
int cost[20][20];
int dp[(1<<18) + 1][20];
int n;
int main()
{
    ifstream cin("hamilton.in");
    ofstream cout("hamilton.out");
    int m, a, b, c, ok = 0, vec;
    cin >> n >> m;
    adj.resize(n + 1);
    for(int i = 0; i < m; i++){
        cin >> a >> b >> c;
        adj[a].push_back(b);
        cost[a][b] = c;
    }
    for(int conf = 1; conf < (1<<n); conf+=2){
        for(int nod = 0; nod < n; nod++){
            dp[conf][nod] = 2100000000;
        }
    }
    dp[1][0] = 0;
    for(int conf = 1; conf < (1<<n); conf+=2){
        for(int nod = 0; nod < n; nod++){
            if(((conf>>nod) & 1) == 1){
                for(int i = 0; i < adj[nod].size(); i++){
                    vec = adj[nod][i];
                    if(((conf>>vec)&1) == 0){
                        dp[(conf | (1<<vec))][vec] = min(dp[(conf | (1<<vec))][vec], dp[conf][nod] + cost[nod][vec]);
                    }
                }
            }
        }
    }
    int ans = 2100000000;
    for(int i = 1; i < n; i++){
        if(cost[i][0] != 0  &&  dp[(1<<n) - 1][i] != 2100000000){
            ans = min(ans, dp[(1<<n) - 1][i] + cost[i][0]);
            ok = 1;
        }
    }
    if(ok == 1)
        cout << ans;
    else
        cout << "Nu exista solutie";
    return 0;
}