#include <bits/stdc++.h>

using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const int nmax = 20;
const int INF = 2000000000;
int N,M,cost[nmax][nmax];
int dp[(1 << 18) + 5][nmax],ans = INF;
vector < int > L[nmax];


inline void Read()
{
    int x,y,c;
    fin >> N >> M;
    while(M--)
    {
        fin >> x >> y >> c;
        cost[x][y] = c;
    }
}


inline void Dinamic()
{
    int i,j,k,stare,Mx;
    Mx = (1 << N);
    for(i = 1; i <= Mx; i++)
        for(j = 0; j < N; j++)
            dp[i][j] = INF;
    dp[1][0] = 0;
    for(i = 1; i < Mx; i++)
        for(j = 0; j < N; j++)
    {
        if(dp[i][j] == INF) continue;
        for(k = 0; k < N; k++)
        {
            if(!((1 << k) & i) && cost[j][k])
                dp[i | (1 << k)][k] = min(dp[i | (1 << k)][k],dp[i][j] + cost[j][k]);
        }
    }
    for(i = 1; i < N; i++)
        if(cost[i][0] && dp[Mx-1][i] != INF)
            ans = min(ans,dp[Mx-1][i] + cost[i][0]);
    if(ans == INF) fout << "Nu exista solutie\n";
    else fout << ans << "\n";
    fout.close();
}


int main()
{
    Read();
    Dinamic();
    return 0;
}