#include <fstream>
#include <vector>
#include <string.h>

#define INF 2000000000
#define nMax 18
#define confMax (1 << 18)
#define pb push_back
#define mkp make_pair

using namespace std;

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

int n, m;
int dp[nMax][confMax];
vector<pair<int, int> > G[nMax];

int memo(int node, int conf)
{
    if(dp[node][conf]==-1)
    {
        dp[node][conf]=INF;
        for(vector<pair<int, int> >::iterator it=G[node].begin(); it!=G[node].end(); it++)
        {
            int fiu=it->first, cost=it->second;
            if(conf & (1 << fiu))
            {
                if(fiu==0 && conf!=(1 << node)+1)
                    continue;
                dp[node][conf]=min(dp[node][conf], memo(fiu, conf ^ (1 << node))+cost);
            }
        }
    }
    return dp[node][conf];
}

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

    memset(dp, -1, sizeof(dp));
    dp[0][1]=0;

    int Sol=INF;
    int limit=(1 << n)-1;
    for(vector<pair<int, int> >::iterator it=G[0].begin(); it!=G[0].end(); it++)
    {
        int fiu=it->first, cost=it->second;
        Sol=min(Sol, memo(fiu, limit)+cost);
    }

    (Sol!=INF ? fout<<Sol : fout<<"Nu exista solutie");
}