#include <bits/stdc++.h>

using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const long long nrmare = 1e18+9;

long long n, m, dp[262145][18];

vector<pair<int, int>> veciniinvers[18];

int main()
{
    fin>>n>>m;
    for(int i = 1; i <= m; ++i)
    {
        int x, y, cost;
        fin>>x>>y>>cost;
        veciniinvers[y].push_back({x, cost});
    }

    int tot = (1<<n) - 1;
    for(int i = 1; i <= tot; ++i)
    {
        for(int j = 0; j < n; ++j)
            dp[i][j] = nrmare;
    }

    dp[1][0] = 0;
    for(int m = 2; m <= tot; ++m)
    {
        for(int i = 0; i < n; ++i)
        {
            if((m & (1<<i)) == 0)
                continue;

            for(auto nod : veciniinvers[i])
            {
                if((m & (1<<nod.first)) == 0)
                    continue;
                dp[m][i] = min(dp[m][i], dp[m-(1<<i)][nod.first] + nod.second);
            }
        }
    }
    long long mini = nrmare;

    for(auto i : veciniinvers[0])
    {
        long long rez = dp[tot][i.first] + i.second;
        mini = min(mini, rez);
    }
    if(mini == nrmare)
        fout<<"Nu exista solutie";
    else
        fout<<mini;

    return 0;
}