#include <fstream>
#include <vector>
#include <climits>
#include <cstring>
using namespace std;
ifstream fin ("hamilton.in");
ofstream fout ("hamilton.out");
vector < int > V[20];
int c,n,m,x,y,i,j,d[20][20];
int dp[ 1 << 18][18];
int answ = 1000000000;
int fct (int c,int l)
{
    if (dp[c][l] == -1)
    {
        dp[c][l] = answ;
        for (auto e : V[l])
            if (c & (1 << e))
            {
                /*if (e == 0 && c!=(1<< l) + 1)
                    continue;*/
                dp[c][l] = min(dp[c][l],fct(c^(1 << l),e) + d[e][l]);
            }
    }
    return dp[c][l];
}
int main()
{
    ios::sync_with_stdio(false);
    fin.tie(0);
    fout.tie(0);
    fin >> n >> m;
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            d[i][j] = answ;
    for (i=1;i<=m;i++)
    {
        fin >> x >> y >> c;
        V[y].push_back(x);
        d[x][y] = c;
    }
    memset(dp,-1,sizeof(dp));
    dp[1<<0][0] = 0;
    for (auto e : V[0])
        answ = min(answ,fct((1<<n)-1,e) + d[e][0]);
    if (answ == 1000000000)
        fout << "Nu exista solutie";
    else
        fout << answ;
    return 0;
}