#include <cstdio>
#include <vector>
#define inf 0xfffff
#define put2(k) (1<<k)
#define minim(a,b) (a<b)?(a):(b)
using namespace std;
 
vector <int> a[20];
vector <int> :: iterator it;
unsigned int cost[20][20];
unsigned int v[300000][20];
int n,m;
 
unsigned int hamilton(int k) {
    for (int i=1;i<=put2(n)-1;i++) {
        for (int j=0;j<n;j++) {
            if (i==1 && j==0) v[i][j] = 0;
            else v[i][j] = inf;
            if ((i & put2(j)) != 0) {
                for (it = a[j].begin();it != a[j].end();it++) {
                    int putere = put2(*it);
                    if ((i & putere) != 0) 
                        if (v[i^put2(j)][*it] != inf) v[i][j] = minim(v[i][j],cost[*it][j] + v[i^put2(j)][*it]);
                }
            }
        }
    }
    unsigned int dist = inf;
    for (it = a[0].begin();it != a[0].end();it++) {
        if (v[put2(n)-1][*it] != inf) dist = minim(dist,v[put2(n)-1][*it]+cost[*it][0]);
    }
    return dist;
}
 
int main() {
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    scanf("%d %d",&n,&m);
    for (int i=1;i<=m;i++) {
        int d,b,c;
        scanf("%d %d %d",&d,&b,&c);
        cost[d][b] = c;
        a[b].push_back(d);
    }
    unsigned int res = hamilton(1);
    if (res != inf) printf("%u\n",res);
    else printf("Nu exista solutie\n");
    return 0;
}