#include <stdio.h>
#include <vector>

inline int min(int a,int b)
{
    if(a<b)
        return a;
    return b;
}

FILE *f1 = fopen("hamilton.in","r");
FILE *f2 = fopen("hamilton.out","w");

const int inf = 100000005;
const int N = 18;

int n,m,i,j,k,a,b,cost;
int c[N][N], d[1<<N][N];

std::vector<int> g[N];

int main()
{
    fscanf(f1,"%d%d",&n,&m);

    for(i=0;i<m;i++)
    {
        fscanf(f1,"%d%d%d",&a,&b,&cost);

        g[b].push_back(a);
        c[a][b] = cost;
    }

    for(i=0;i < (1<<n); i++)
        for(j=0;j<n;j++)
            d[i][j] = inf;

    d[1][0] = 0;

    for(i=0;i < (1<<n); i++)
        for(j=0;j<n;j++)
            if(i & (1<<j))
            {
                //if(d[i][j] == 0)
                    //d[i][j] = inf;

                for(k=0; k<g[j].size(); k++)
                    if(i & (1<<g[j][k]))
                    {
                        d[i][j] = min(d[i][j] ,d[i^(1<<j)][g[j][k]] + c[g[j][k]][j]);
                    }
            }


    int sol = inf;
    int nr = (1<<n)-1;
    int l = g[0].size();
    int y;

    for(i=0;i<l;i++)
    {
        y = g[0][i];

        sol = min(sol , d[nr][y] + c[y][0]);
    }

    if(sol == inf)
        fprintf(f2,"Nu exista solutie");

    else
        fprintf(f2,"%d",sol);

    return 0;
}