#include <bits/stdc++.h>
#define dimn 20
#define dimm 262150
#define mask ((1<<N)-1)
#define inf ((int)2e9)

std::ifstream f("hamilton.in");
std::ofstream g("hamilton.out");

int N, M;
int cost[dimn][dimn];
std::list <int> adj[dimn];
int dp[dimm][dimn];

int calc(int bset, int last) {
    if(dp[bset][last] == -1) {
        dp[bset][last] = inf;

        for (auto vec:adj[last]) {
            if(bset & (1 << vec)) {
                if(vec == 0 && bset != (1<<(last)) + 1) continue;
                dp[bset][last] = std::min(dp[bset][last], calc(bset ^ (1<<last), vec) +  cost[vec][last]);
            }
        }
    } return dp[bset][last];
}

void citire() {
    f >> N >> M;
    for (int i=0, j; i<N; i++)
        for (j=0; j<N; j++)
            cost[i][j] = inf;
    for (int i=0, x, y, c; i<M; i++) {
        f >> x >> y >> c;
        adj[y].push_back(x);
        cost[x][y] = c;
    }
}
void rezolvare() {
    memset(dp, -1, sizeof(dp));
    dp[1][0] = 0;

    int res = inf;
    for (auto it:adj[0])
        res = std::min(res, calc((1<<N)-1, it) + cost[it][0]);
    if(res == inf) g << "Nu exista solutie\n";
    else g << res << "\n";
}

int main()
{
    citire();
    rezolvare();

    return 0;
}