#include <iostream>
#include <fstream>

using namespace std;

ifstream in("hamilton.in");
ofstream out("hamilton.out");

const int N = 18;
const int M = N*(N-1);
const int INF = 1e9;
const int N2 = (1<<N);
int n, m, x, y, c, nr, d[N2][N], cost[N][N];
int vf[M], urm[M], lst[N];
int ans = INF;

void adauga(int x, int y)
{
    vf[++nr] = y;
    urm[nr] = lst[x];
    lst[x] = nr;
}

int main()
{
    in>>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++)
            d[i][j] = INF;

    for(int i=1; i<=m; i++)
    {
        in>>x>>y>>c;
        cost[x][y] = c;
        adauga(x, y);
    }

    d[1][0] = 0;
    for(int i=3; i < (1<<n); i+=2)
        for(int j=0; j<n; j++)
            if(i & (1<<j))
            {
                int ii = (i ^ (1<<j));
                for(int k=0; k<n; k++)
                {
                    if(i & (1<<k))
                    {
                        d[i][j] = min(d[i][j], d[ii][k] + cost[k][j]);
                    }
                }
            }

    for(int j=1; j<n; j++)
        ans = min(ans, d[(1<<n)-1][j] + cost[j][0]);
    if(ans == INF)
        out<<"Nu exista solutie";
    else out<<ans;
    return 0;
}