/// circular
/// patratele
#include <bits/stdc++.h>
using namespace std;

#define MOD 666013
#define INF INT_MAX/2

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

int i, n, m, mat[20][20], j, y, x, c, vf, q[20], dp[1 << 20][20], k;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    fin >> n >> m;
    for(i=0; i<(1 <<n); i++)
        for(j=0; j<=n; j++)
            dp[i][j]=INF;
    dp[1][0]=0;
    for (i = 1; i <= m; i++)
    {
        fin >> x >> y >> c;
        mat[x][y] = c;
    }
    for (i = 1; i <(1 <<n); i++)
    {
        vf = 0;
        for (j = 0; j < n; j++)
            if (i & (1 << j))
                q[vf++] = j;
        for (j = 0; j < vf; j++)
            for (y = 0; y < vf; y++)
            {
                if (mat[q[j]][q[y]] && dp[i ^ (1 << q[y])][q[j]] != INF)
                    dp[i][q[y]] = min(dp[i ^ (1 << q[y])][q[j]] + mat[q[j]][q[y]], dp[i][q[y]]);
            }
    }
    int ras = INF;
    for (i = 0; i < n; i++)
        if(mat[i][0])
            ras = min(ras, dp[(1 <<n) - 1][i]+mat[i][0]);
    if(ras!=INF)
        fout<<ras;
    else
        fout<<"Nu exista solutie";

    return 0;
}