#include <bits/stdc++.h>

using namespace std;
const int oo = 2e9;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int n, m;
int a[20][20];
int dp[20][(1 << 18) + 2]   ;

int main()
{
    int i, j, x, masca;
    fin >> n >> m;
    int N = (1 << n);
    for(i = 1;i <= m;i++)
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        a[x][y] = cost;
    }
    for(i = 0;i < n;i++)
        for(j = 0;j < N;j++)
            dp[i][j] = oo;
    dp[0][1] = 0;
    for(masca = 3;masca < N;masca += 2)
        for(i = 1 ;i < n;i++)
            if(masca & (1 << i))
            {
                x = masca ^ (1 << i);
                for(j = 0;j < n;j++)
                    if((x & (1 << j)) && (a[j][i] > 0))
                        dp[i][masca] = min(dp[i][masca], dp[j][x] + a[j][i]);
            }
    x = oo;
    for(i = 1;i < n;i++)
        if(dp[i][N - 1] < oo && a[i][0] > 0)
            x = min(x, dp[i][N - 1] + a[i][0]);
    if(x == oo)
    {
        fout << "Nu exista solutie";
        return 0;
    }
    fout << x << "\n";
    return 0;
}