#include <bits/stdc++.h>
#define oo 1<<30

using namespace std;

vector<int> v[19];
int cost[19][19]={0};
int d[1<<19][19];

char buff[200000];int pos=0;
FILE*f=freopen("hamilton.in","r",stdin);
FILE*g=freopen("hamilton.out","w",stdout);
inline void read(int &nr){
    while(buff[pos] < '0' || buff[pos] > '9')if(++pos == 200000) fread(buff, 1, 200000, stdin), pos = 0;
    nr = 0;
    while('0' <= buff[pos] && buff[pos] <= '9') {nr = nr * 10 + buff[pos] - '0';if(++pos == 200000) fread(buff, 1, 200000, stdin), pos = 0;}
}

int solve(int cfg, int b){
    if(d[cfg][b] != -1)
        return d[cfg][b];

    d[cfg][b] = oo;
    int i, lg = v[b].size();
    for(i=0; i<lg; i++)
        if(cfg & (1<<v[b][i]))
            if(v[b][i] || (cfg ^ (1<<b) != 1))
                d[cfg][b] = min(d[cfg][b], solve(cfg ^ (1<<b), v[b][i]) + cost[v[b][i]][b]);
    return d[cfg][b];
}

int main()
{
    int n, m, i, j, a, b, c;
    read(n); read(m);
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            cost[i][j] = oo;
    for(i=1; i<=m; i++){
        read(a); read(b); read(c);
        v[b].push_back(a);
        cost[a][b] = c;
    }
    for(i=1; i<(1<<n); i++)
        for(j=0; j<n; j++)
            d[i][j] = -1;
    int sol = oo;
    d[1][0] = 0;
    for(i=0; i<v[0].size(); i++)
        sol = min(sol, solve((1<<n)-1, v[0][i]) + cost[v[0][i]][0]);
    if(sol != oo) printf("%d\n", sol);
    else printf("Nu exista solutie\n");
}