#include <fstream>
#include <vector>

using namespace std;

ifstream cin("hamilton.in");
ofstream cout("hamilton.out");

const int NMAX = 18;
const int MASKMAX = (1 << NMAX);

const int INF = 1e9;

int N, M;
vector < pair <int,int> > g[NMAX + 2];

int dp[MASKMAX + 1][NMAX + 2];

int main()
{
    cin >> N >> M;

    for(int i = 1; i <= M; i++)
    {
        int x, y, c;
        cin >> x >> y >> c;
        g[y].push_back({x, c});
    }

    for(int msk = 0; msk < (1 << N); msk++)
        for(int i = 0; i < N; i++)
            dp[msk][i] = INF;

    dp[1][0] = 0;

    for(int msk = 2; msk < (1 << N); msk++)
        for(int f = 1; f < N; f++)
            if(msk & (1 << f))
                for(auto it : g[f])
                    if(msk & (1 << it.first))
                        dp[msk][f] = min(dp[msk][f], dp[msk ^ (1 << f)][it.first] + it.second);

    int mins = INF;

    for(auto it : g[0])
        mins = min(mins, dp[(1 << N) - 1][it.first] + it.second);

    if(mins == INF)
        cout << "Nu exista solutie\n";
    else
        cout << mins << '\n';

    return 0;
}