#include <stdio.h>
#include <vector>
#include <iostream>
using namespace std;
FILE *in,*out;

int n,m,inf=100000002;
int cost[28][28];
int c[275500][28];
vector <int> graph[28];

void read() {
    fscanf(in,"%d %d",&n,&m);
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cost[i][j]=inf;
    for(int i=0; i<1<<n; i++)
        for(int j=0; j<n; j++)
            c[i][j]=inf;
    int x,y;
    for(int i=1; i<=m; i++) {
        fscanf(in,"%d %d",&x,&y);
        graph[y].push_back(x);
        fscanf(in,"%d",&cost[x][y]);
    }
}

int main() {
    in=fopen("hamilton.in","r");
    out=fopen("hamilton.out","w");
    read();
    c[1][0]=0;
    for(int i=1; i<1<<n; i++)
        for(int j=0; j<n; j++)
            if(i&(1<<j))
                for(int k=0; k<graph[j].size(); k++)
                    if(i&(1<<graph[j][k]))
                        c[i][j]=min(c[i][j],c[i^(1<<j)][graph[j][k]]+cost[graph[j][k]][j]);
    int sol=inf;
    for(int k=0; k<graph[0].size(); k++)
        sol=min(sol,c[(1<<n)-1][graph[0][k]]+cost[graph[0][k]][0]);
    if(sol==inf)
        fprintf(out,"Nu exista solutie");
    else
        fprintf(out,"%d",sol);
    return 0;
}