#include <bits/stdc++.h>

using namespace std;
#define nmax 20

int main()
{
    ifstream fin("hamilton.in");
    ofstream fout("hamilton.out");

    int n,m;
    int costuri[nmax][nmax];
    int dp[1<<nmax][nmax];
    vector<int> in[nmax];

    fin>>n>>m;
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            costuri[i][j] = 1e9;
        }
    }

    int a,b,c;
    for (int i=0;i<m;i++)
    {
        fin>>a>>b>>c;
        costuri[a][b] = c;
        in[b].push_back(a);
    }


    for (int mask=1;mask<(1<<n);mask++)
    {
        for (int i=0;i<n;i++)
        {
            dp[mask][i] = 1e9;
        }
    }

    dp[1][0] = 0;
    for (int mask=1;mask<(1<<n);mask++)
    {
        for (int i=1;i<n;i++)
        {
            if (mask & (1<<i))
            {
                for (int k=0;k<in[i].size();k++)
                {
                    int j = in[i][k];
                    dp[mask][i] = min(dp[mask][i],dp[mask-(1<<i)][j]+costuri[j][i]);
                }
            }
        }
    }

    int res = 1e9;
    for (int i=1;i<n;i++)
    {
        res = min(res,dp[(1<<n)-1][i]+costuri[i][0]);
    }

    if (res == 1e9)
    {
        fout<<"Nu exista solutie";
    }
    else
    {
        fout<<res;
    }

    fin.close();
    fout.close();
    return 0;
}