#include <fstream>
#include <vector>

using namespace std;

ifstream in("hamilton.in");
ofstream out("hamilton.out");
int n, m;
int v[25][25];
vector<int> vec[20];
int dp[262150][20];
int INF = 1e9;

int main()
{
    in>>n>>m;

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

        v[x][y] = c;
        vec[y].push_back(x);
    }

    int stmax = (1 << n);

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

    //vector<vector<int>> dp(1 << n, vector<int>(n, 1e9));

    dp[1][0] = 0;

    for(int i = 3; i<stmax; i += 2)
    {
        for(int j = 1; j<n; j++)
        {
            if(i & (1 << j))
            {
                /*for(int k = 1; k<n; k++)
                {
                    if(v[k][j] != 0)
                    {
                        //out<<k<<" "<<j<<'\n';
                        dp[i][j] = min(dp[i][j], dp[i - (1 << j)][k] + v[k][j]);
                    }
                }*/

                for(auto k: vec[j])
                {
                    dp[i][j] = min(dp[i][j], dp[i - (1 << j)][k] + v[k][j]);
                }
            }
        }
    }

    int ans = INF;
    for(int i = 1; i<n; i++)
    {
        if(v[i][0] != 0)
        {
            ans = min(ans, dp[stmax - 1][i] + v[i][0]);
            //out<<dp[stmax - 1][i] + v[i][0]<<'\n';
        }
    }

    if(ans == INF)
    {
        out<<"Nu exista solutie";
    }
    else
    {
        out<<ans;
    }

    return 0;
}