#include <fstream>
#include <vector>
#define MIN(a, b) (((a)<(b))?(a):(b))

const int N = 20;
const int M = (1<<18) + 5;
const int inf = 2e9;

int adj[N][N], dp[N][M];
std::vector<int>l[N];

void init() {
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            adj[i][j] = inf;
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
            dp[i][j] = inf;
}
int main () {
    std::ifstream fin("hamilton.in");
    std::ofstream fout("hamilton.out");
    int n, m, from, to, ans = inf;
    fin>>n>>m;
    init();
    for(int i=1;i<=m;i++) {
        fin>>from>>to;
        l[to].push_back(from);
        fin>>adj[from][to];
    }
    dp[0][1] = 0;
    for(int mask=0;mask<(1<<n); mask++)
        for(int node=0;node<n;node++) if(mask&(1<<node))
            for(int prev:l[node]) if(mask&(1<<prev))
                dp[node][mask] = MIN(dp[node][mask], dp[prev][mask^(1<<node)] + adj[prev][node]);
    for(int last:l[0]) ans = MIN(ans, dp[last][(1<<n)-1] + adj[last][0]);
    if(ans == inf) fout<<"Nu exista solutie\n";
    else fout<<ans;
}