#include <bits/stdc++.h>

std :: ifstream in ("hamilton.in");

std :: ofstream out ("hamilton.out");

const int NMAX = 25;

const int INF = 1e9;

int n;

int m;

int x;

int y;

int d;

int ret;

int ans = INF;

int adj[NMAX][NMAX];

int dp[(1 << 18)][NMAX];

int hamilton()
{
    dp[1][0] = 0;

    for(int mask = 3; mask < (1 << n); mask ++)
    {
        for(int i = 0; i < n; i ++)
        {
            if(mask & (1 << i))
            {
                for(int j = 0; j < n; j ++)
                {
                    if(mask & (1 << j))
                    {
                        dp[mask][i] = std :: min(dp[mask][i], dp[mask ^ (1 << i)][j] + adj[j][i]);
                    }
                }
            }
        }
    }

    for(int i = 0; i < n; i ++)
    {
        ans = std :: min(ans, dp[(1 << n) - 1][i] + adj[i][0]);
    }

    if(ans == INF)
    {
        return -1;
    }

    return ans;
}

int main()
{

    in >> n >> m;

    for(int i = 0; i < n; i ++)
    {
        for(int j = 0; j < n; j ++)
        {
            adj[i][j] = INF;
        }
    }

    for(int i = 1; i <= m; i ++)
    {
        in >> x >> y >> d;

        adj[x][y] = d;
    }

    for(int i = 0; i < (1 << 18); i ++)
    {
        for(int j = 0; j < n; j ++)
        {
            dp[i][j] = INF;
        }
    }


    ret = hamilton();

    if(ret == -1)
    {
        out << "Nu exista solutie";
    }
    else
    {
        out << ret;
    }

    return 0;
}