#include <cstdio>
#include <algorithm>
#include <cstring>

#include <vector>

#define Nmax ((1<<18)+666)
#define INF 0x3f3f3f3f

using namespace std;

vector<int> G[20];
int cost[20][20],N,M;
int DP[20][Nmax]; /// DP[i][j] -> costul minim de a ajunge in nodul i trecand prin maska j


void read ( void )
{
    scanf("%d%d",&N,&M);
    int a,b,c;
    for(int i = 1; i <= M; ++i){
        scanf("%d%d%d",&a,&b,&c);
        G[b].push_back(a);
        cost[a][b] = c;
    }
}

int dynamic (int nod, int mask)
{
    if(DP[nod][mask] != -2100000000)
        return DP[nod][mask];

    int crt = INF;
    for(vector<int>::iterator it = G[nod].begin(); it != G[nod].end(); ++it)
            if(mask & (1<<*it))
                if(*it != 0 || *it == 0 && mask > 1)
                    crt = min( crt , dynamic(*it,mask^(1<<nod)) + cost[*it][nod]);
    DP[nod][mask] = crt;
    return DP[nod][mask];
}

void prepare ( void )
{
    for(int i = 0; i < N; ++i)
        for(int j = 0; j < Nmax - 1; ++j)
            DP[i][j] = -2100000000;
    DP[0][1] = 0;
}

void solve ( void )
{
    int best = INF;
    for(vector<int>::iterator it = G[0].begin(); it != G[0].end(); ++it)
            best = min(best, dynamic(*it,(1<<N)-1) + cost[*it][0]);
    if(best >= INF)
    {
        printf("Nu exista solutie\n");
        return;
    }
    printf("%d\n",best);
}

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

    read();
    prepare();
    solve();

    return 0;
}