#include <bits/stdc++.h>
using namespace std;
ifstream f ("hamilton.in");
ofstream g ("hamilton.out");

const int inf = 1e9;
int n, m, cost[20][20], dp[(1<<18)][20];

int main()
{
    f >> n >> m;
    if(n == 1) {
        g << 0;
        return 0;
    }
    int sol = inf;
    while(m--){
        int x, y;
        f >> x >> y >> cost[x][y];
    }
    for(int i = 0; i < (1 << n); ++i)
        for(int j = 0; j < n; ++j)
            dp[i][j] = inf;
    dp[1][0]=0;
    for(int i = 1;i < (1 << n); ++i)
        for(int j = 0; j < n; ++j){
            if(dp[i][j] == inf) continue;
            for(int k = 0; k < n; ++k)
                if(!((1 << k) & i) && cost[j][k])
                    dp[i + (1 << k)][k] = min(dp[i + (1 << k)][k], dp[i][j] + cost[j][k]);
        }
    for(int i = 1; i < n; ++i)
        if(cost[i][0]) sol = min(sol, dp[(1 << n) - 1][i] + cost[i][0]);
    if(sol == inf) g << "Nu exista solutie";
    else g << sol;
    return 0;
}