#include <fstream>
#include <vector>
#define ll long long
#define pb push_back
using namespace std;
ifstream cin ("hamilton.in");
ofstream cout ("hamilton.out");
vector <ll> g[20];
ll dp[1<<18][18];
ll n,m;
ll answ = 2e9;
ll dist[19][19];
ll calculare (ll masca,ll vf)
{
    if (dp[masca][vf] == -1)
    {
        dp[masca][vf] = 2e9;
        for (auto ult:g[vf])
            if ((1<<ult)&masca)
                dp[masca][vf] = min(dp[masca][vf],calculare(masca^(1<<vf),ult) + dist[vf][ult]);
    }
    return dp[masca][vf];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll i,j;
    cin >> n >> m;
    for (i=0;i<n;i++)
        for (j=0;j<n;j++)
            dist[i][j] = 2e9;
    for (i=1;i<=m;i++)
    {
        ll x,y,c;
        cin >> x >> y >> c;
        g[y].pb(x);
        dist[y][x] = c;
    }
    for (i=0;i<(1<<n);i++)
        for (j=0;j<n;j++)
            dp[i][j] = -1;
    dp[1<<0][0] = 0;
    for (auto vf:g[0])
        answ = min(answ,calculare(((1<<n)-1),vf) + dist[0][vf]);
    if (answ == 2e9)
        cout << "Nu exista solutie";
    else
        cout << answ;
    return 0;
}