#include <bits/stdc++.h>

using namespace std;

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


const int InF = 100000000;
const int mAXn = 20;

int n, m, sol;
int cost[18][18];
int dp[1 << 18][18];
int main()
{
    fin >> n >> m;
    sol = InF;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cost[i][j] = InF;

    for(int i = 1; i <= m; i++)
    {
        int x, y;
        fin >> x >> y;
        fin >> cost[x][y];
    }
    for(int conf = 0; conf < (1<<n); conf++)
        for(int nod = 0; nod < n; nod++)
            dp[conf][nod] = InF;
    for(int conf = 1; conf < (1 << n); conf++)
    {
        for(int nod = 0; nod < n; nod++)
        {
            if(dp[conf][nod] == InF)
                continue;
            for(int vecin = 0; vecin < n; vecin++)
            {
                if (cost[nod][vecin] == InF)
                    continue;
                if (((conf >> vecin) & 1) == 0)
                {
                    int nou = conf | (1 << vecin);
                    int val = dp[conf][nod] + cost[nod][vecin];
                    if (val < dp[nou][vecin])
                        dp[nou][vecin] = val;
                }
            }
        }
    }
    int ans = InF;
    for(int nod = 0; nod < n; nod ++)
    {
        if(dp[(1<<n)-1][nod] != InF and cost[nod][0] != InF)
        {
            int val = dp[(1 << n) -1][nod] + cost[nod][0];
            ans = min(ans, val);
        }
    }
    if(ans == InF)
        fout << "Nu exista solutie";
    else
        fout << ans;
    return 0;
}