#include <fstream>
#include <vector>

using namespace std;

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

const int maxN = 20, inf = 0x3f3f3f3f;
int cost[maxN][maxN], n, m, dp[262150][maxN], ans;
vector <int> G[maxN];

void citire()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int a, b, c;
        fin >> a >> b >> c;
        cost[a][b] = c;
        G[b].push_back(a);
    }
}

void solve()
{
    for(int i = 0; i < (1 << n); i++)
        for(int j = 0; j < n; j++)
            dp[i][j] = inf;
    dp[1][0] = 0;
    for(int i = 1; i < (1 << n); i++)
        for(int j = 0; j < n; j++)
            if(i && (1 << j))
                for(auto k : G[j])
                    if(i && (1 << k))
                        dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][k] + cost[k][j]);
    ans = inf;
    for(auto vecin : G[0])
        ans = min(ans, dp[(1 << n) - 1][vecin] + cost[vecin][0]);
    if(ans == inf)
        fout << "Nu exista solutie";
    else
        fout << ans << '\n';
}

int main()
{
    citire();
    solve();
    return 0;
}