#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in ("hamilton.in");
ofstream out("hamilton.out");
int const N=20,POw=275000;
vector <int> v[N];//,cost[N];
int n,m,d[POw][N];
int cost[N][N];
int const INF=200000000;
void citire()
{
   in>>n>>m;   int x,y,c;
    for(int i=1;i<=m;i++)
    {
        in>>x>>y>>c;
        v[y].push_back(x);
        //cost[x].push_back(c);
        cost[x][y]=c;
    }
}
void init()
{
    for(int i=0;i<(1<<n);i++)
        for(int j=0;j<n;j++)
            d[i][j]=INF;
    d[1][0]=0;
}
void rez()
{
    int doi=1<<n;   int p;
    for(int i=1;i<doi;i+=2)
        for(int j=0;j<n;j++)
            if(i&(1<<j))
            {
                for(size_t k=0;k<v[j].size();k++)
                {
                    p=v[j][k];
                    if((i&(1<<p))!=0)
                        if(d[i^(1<<j)][p]+cost[p][j]<d[i][j])
                            d[i][j]=d[i^(1<<j)][p]+cost[p][j];
                }

            }
}
void afis()
{
    for(int i=1;i<(1<<n);i++)
    {
        for(int j=0;j<n;j++)
            out<<d[i][j]<<" ";
        out<<"\n";
    }
}
int main()
{
    citire();
    init();
    rez();  int r=INF;
    //afis(); return 0;
    int p,aux = 1<<n;
    aux--;
    for(int i=0;i<v[0].size();i++)
    {
        p=v[0][i];
        r=min(r,d[aux][p]+cost[p][0]);
    }
    if(r==INF){out<<"Nu exista solutie\n";}
    else    out<<r<<"\n";
    return 0;
}