#include<fstream>
#include<vector>
using namespace std;

vector<int> A[26];
int cost[26][26];
int b[300000][26];

int main()
{
    int n,i,j,x,y,m,sol;
    FILE *f=fopen("hamilton.in","rt");
    FILE *g=fopen("hamilton.out","wt");

    fscanf(f,"%d %d",&n,&m);
    for (i = 0; i < n; ++i)
        for (j = 0; j < n; ++j) cost[i][j] = 100000000;

    for (i = 1; i <= m; ++i)
    {
    fscanf(f,"%d %d",&x,&y);
    A[y].push_back(x);
    fscanf(f,"%d",&cost[x][y]) >> cost[x][y];
    }

    for (i=0 ; i < 1 << n ; ++i)
        for (j=0 ; j<n ; ++j)
            b[i][j] = 100000000;

    b[1][0] = 0;

   for (i=0 ; i < 1 << n ; ++i)
       for (j = 0; j < n; ++j)
           if (i & (1<<j))
       for (size_t k = 0; k < A[j].size(); ++k)
            if (i & (1<<A[j][k]))
                b[i][j] = min(b[i][j], b[i ^ (1<<j)][ A[j][k] ] + cost[ A[j][k] ][j]);

sol = 100000000;
for (size_t i = 0; i < A[0].size(); ++i)
sol = min(sol, b[(1<<n) - 1][ A[0][i] ] + cost[ A[0][i] ][0]);

if (sol == 100000000) fprintf(g,"Nu exista solutie\n");
else fprintf(g,"%d\n",sol);

return 0;
}