#include <bits/stdc++.h>
using namespace std;

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

struct Elem
{
    int dest, cost;
};

vector <Elem> v[20];

int dp[20][300005];

int main()
{
    int N, M;

    fin >> N >> M;

    for(int i = 1; i <= M; i++)
    {
        int x, y, z;

        fin >> x >> y >> z;

        v[x].push_back({y, z});
    }

    for(int i = 0; i < N; i++)
        for(int j = 1; j <= (1 << N); j++)
            dp[i][j] = INT_MAX;

    for(int i = 0; i < N; i++)
        dp[i][(1 << i)] = 0;

    for(int mask = 1; mask <= (1 << N) - 1; mask++)
    for(int j = 0; j < N; j++)
    {
        if(dp[j][mask] == INT_MAX)
            continue;

        for(int i = 0; i < v[j].size(); i++)
            if((mask & (1 << v[j][i].dest)) == 0)
        {
            int val = (mask | (1 << v[j][i].dest));

            if(val == 11)
                val++, val--;

            dp[v[j][i].dest][val] = min(dp[v[j][i].dest][val], dp[j][mask] + v[j][i].cost);
        }
    }

    int ans = INT_MAX;

    if(dp[0][(1 << N) - 1] == INT_MAX)
        fout << "Nu exista solutie";
    else
        {
            //fout << ans;

            for(auto it : v[0])
              ans = min(ans, dp[0][(1 << N) - 1] + it.cost);

            fout << ans;
        }
    return 0;
}