#include <cstdio>
#include <vector>
#define N 18

using namespace std;

int n,m,i,j,b,B,k,c[N][N],C[N][1<<17],M,sol;
vector<int> X, Y;

int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);

    scanf("%d%d",&n,&m);

    for(;m;m--)
    {
        scanf("%d%d",&i,&j);
        scanf("%d",&c[i][j]);
    }

    k = n-1;

    for(i=1,j=0;j<k;i<<=1,j++)
        if(c[k][j])
            C[j][i] = c[k][j];

    M = (1<<k)-1;

    for(b=1;b<M;b++)
    {
        X.resize(0);
        Y.resize(0);
        for(i=1,j=0;j<k;i<<=1,j++)
        {
            if(b&i)
            {
                if(C[j][b])
                    X.push_back(j);
            }
            else
                Y.push_back(j);
        }
        for(auto x:X)
            for(auto y:Y)
                if(c[x][y])
                {
                    B = b|(1<<y);
                    if(!C[y][B])
                        C[y][B] = C[x][b] + c[x][y];
                    else
                        if(C[y][B] > C[x][b] + c[x][y])
                            C[y][B] = C[x][b] + c[x][y];
                }
    }
    sol = 20000000;
    for(i=0;i<k;i++)
        if(C[i][M]&&c[i][k])
            if(sol > C[i][M] + c[i][k])
                sol = C[i][M] + c[i][k];
    if(sol < 20000000)
        printf("%d",sol);
    else printf("Nu exista solutie\n");
    return 0;
}