#include <iostream>
#include <stdio.h>
using namespace std;
FILE *f,*g;
struct graph
{
    int node, next;
}v[500];
int dp[1<<19][20],cost[20][20];
int start[20];
int n,m;
void read()
{
    int x,y,c,k=0;
    fscanf(f,"%d %d",&n,&m);
    for(int i=1; i<=m; i++)
    {
        fscanf(f,"%d %d %d",&x,&y,&c);
        v[++k].node=x;
        v[k].next=start[y];
        start[y]=k;
        cost[x][y]=c;
    }
}
int minim(int a, int b)
{
    return a<b ? a:b;
}
void solve()
{
    for(int i=0; i<1<<n; i++)
        for(int j=0; j<=n; j++)
            dp[i][j]=9999999;
    dp[1][0]=0;
    for(int i=0; i<(1<<n); i++)
        for(int j=0; j<n; j++)
            if(i & (1<<j))
                for(int k=start[j]; k; k=v[k].next)
                    if(i & (1<<v[k].node))
                        if(dp[i][j]>dp[i-(1<<j)][v[k].node] + cost[v[k].node][j])
                            dp[i][j]=dp[i-(1<<j)][v[k].node] + cost[v[k].node][j];

    int mini=999999999;
    for(int i=start[0]; i; i=v[i].next)
        mini=minim(mini, dp[(1<<n)-1][v[i].node] + cost[v[i].node][0]);

    if(mini==999999999)
        fprintf(g,"Nu exista solutie");
    else
        fprintf(g,"%d",mini);
}
int main()
{
    f=fopen("hamilton.in","r");
    g=fopen("hamilton.out","w");
    read();
    solve();
    fclose(f);
    fclose(g);
    return 0;
}