#include <bits/stdc++.h>

using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const int nmax = 18;
const int inf = 1e8;
int N,M,dp[19][(1 << nmax) + 5];
int C[20][20],ans = inf;

inline void Read()
{
    int i,x,y,z;
    fin >> N >> M;
    for(x = 0; x <= N; x++)
        for(y = 0; y <= N; y++)
            C[x][y] = inf;
    for(i = 1; i <= M; i++)
    {
        fin >> x >> y >> z;
        C[x][y] = z;
    }
}

inline void Solve()
{
    int i,j,stare,S;
    S = (1 << N);
    for(i = 0 ; i < N; i++)
        for(stare = 0; stare < S; ++stare)
            dp[i][stare] = inf;
    dp[0][1] = 0;
    for(stare = 1; stare < S; ++stare)
        for(i = 0; i < N; i++)
            if(dp[i][stare] < inf)
            {
                for(j = 0; j < N; j++)
                    if(C[i][j] < inf && !(stare & (1 << j)))
                        dp[j][stare + (1 << j)] = min(dp[j][stare + (1 << j)],dp[i][stare] + C[i][j]);
            }
    for(i = 1 ; i < N; i++)
            if(C[i][0] < inf)
    {
            ans = min(ans,C[i][0] + dp[i][S-1]);
    }
    if(ans == inf) fout << "Nu exista solutie\n";
    else fout << ans << "\n";
}


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