#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#define INF 100000000
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int n,m,x,y,z,dist[20][262150],cost[20][20]={INF},min1cost=INF;
vector <vector <int>> v(20);
inline int calc (int viz,int last)
{
    if (dist[last][viz]==-1)
    {
        dist[last][viz]=INF;
    for (int j=0; j<v[last].size(); ++j)
    {
        if (viz & (1<<v[last][j]))
        {
            if ((v[last][j]==0 && viz!=(1<<last)+1))
            {

                continue;

            }
            else dist[last][viz]=min(dist[last][viz],calc(viz ^ (1<<last),v[last][j])+cost[v[last][j]][last]);

        }
    }
    }
    return dist[last][viz];
}
int main()
{



    f>>n>>m;
    for (int i=1; i<=m; ++i)
    {
        f>>x>>y>>z;
        v[y].push_back(x);
        cost[x][y]=z;
    }
    memset(dist,-1,sizeof(dist));
    dist[0][1]=0;
    for (int start=0; start<v[0].size(); ++start)
    {

        min1cost=min(min1cost,calc((1<<n)-1,v[0][start])+cost[v[0][start]][0]);
    }
    if (min1cost!=INF)
    g<<min1cost;
    else
    {
        g<<"Nu exista solutie";
    }
    return 0;
}