#include <fstream>
#include <vector>

#define nMax 18
#define configMax (1 << 18)
#define INF 1000000000
#define pb push_back

using namespace std;

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

int n, m;
int dp[configMax][nMax], Cost[nMax][nMax];
vector<int> G[nMax];

int memoizare(int config, int last)
{
    if(dp[config][last]==-1)
    {
        dp[config][last]=INF;
        for(vector<int>::iterator it=G[last].begin(); it!=G[last].end(); it++)
        {
            int fiu=*it;
            if(config & (1 << fiu))
            {
                if(fiu==0 && config!=(1 << last)+1)
                    continue;
                dp[config][last]=min(dp[config][last], memoizare(config ^ (1 << last), fiu)+Cost[fiu][last]);
            }
        }
    }
    return dp[config][last];
}

int main()
{
    int a, b, c;
    fin>>n>>m;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            Cost[i][j]=INF;

    for(int i=0; i<(1 << n); i++)
        for(int j=0; j<n; j++)
            dp[i][j]=-1;

    for(int i=1; i<=m; i++)
    {
        fin>>a>>b>>c;
        G[b].pb(a);
        Cost[a][b]=c;
    }

    dp[1][0]=0;
    int Sol=INF;
    for(vector<int>::iterator it=G[0].begin(); it!=G[0].end(); it++)
    {
        int fiu=*it;
        Sol=min(Sol, memoizare((1 << n)-1, fiu)+Cost[fiu][0]);
    }

    Sol==INF ? fout<<"Nu exista solutie" : fout<<Sol;

}