#include <bits/stdc++.h>

using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const int nmax = 3e5;

int dp[nmax][18], a[20][20], n, m;

int main()
{
    fin>>n>>m;
    for(int i = 1; i <= m; ++i)
    {
        int x, y, c;
        fin>>x>>y>>c;
        a[x][y] = c;
    }

    int tot = (1<<n) - 1;
    for(int i = 0; i <= tot; ++i)
    {
        for(int j = 0; j < n; ++j)
            dp[i][j] = INT_MAX/2;
    }
    dp[1][0] = 0;
    for(int mask = 1; mask <= tot; ++mask)
    {
        for(int crt = 0; (1<<crt) <= mask; ++crt)
        {
            if((mask & (1<<crt)) == 0)
                continue;
            for(int pre = 0; (1<<pre) <= mask; ++pre)
            {
                if((mask & (1<<pre)) == 0 || !a[pre][crt])
                    continue;

                dp[mask][crt] = min(dp[mask][crt], dp[mask ^ (1<<crt)][pre] + a[pre][crt]);
            }
        }
    }
    int ans = INT_MAX/2;
    for(int i = 0; i < n; ++i)
    {
        if(a[i][0])
            ans = min(ans, dp[tot][i] + a[i][0]);
    }
    if(ans == INT_MAX/2)
        fout<<"Nu exista solutie";
    else
        fout<<ans;


    return 0;
}