#include <bits/stdc++.h>

using namespace std;
vector<vector<int>> adj;
int cost[20][20];
long long dp[(1<<18) + 1][20];
int n;
void rec(int conf, int nod){
    int vec;
    for(int i = 0; i < adj[nod].size(); i++){
        vec = adj[nod][i];
        if(((conf>>vec)&1) == 0  &&  dp[(conf | (1<<vec))][vec] == 0){
            dp[(conf | (1<<vec))][vec] = dp[conf][nod] + cost[nod][vec];
            rec((conf | (1<<vec)), vec);
        }else if(((conf>>vec)&1) == 0){
            dp[(conf | (1<<vec))][vec] = min(dp[(conf | (1<<vec))][vec], dp[conf][nod] + cost[nod][vec]);
            rec((conf | (1<<vec)), vec);
        }
    }
}
int main()
{
    ifstream cin("hamilton.in");
    ofstream cout("hamilton.out");
    int m, a, b, c, ok = 0;
    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;
    }
    rec(1, 0);
    long long ans = 210000000000000000;
    for(int i = 1; i < n; i++){
        if(cost[i][0] != 0  &&  dp[(1<<n) - 1][i] != 0){
            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;
}