#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#define MAX 20
#define inf 2000000
ifstream in("hamilton.in");
ofstream out("hamilton.out");
vector <int> v[MAX];
int cost[MAX][MAX];
int d[265000][MAX]; //2^18
int main()
{
    int n,m,i,j,k,s=inf,x,y,z;
    in>>n>>m;
    for(i=0; i<n; i++)
        for(j=0; j<n; j++)
            cost[i][j]=inf;
    for(i=1; i<=m; i++)
    {
        in>>x>>y>>z;
        v[y].push_back(x);
        cost[x][y]=z;
    }
    for(i=0; i<=(1<<n); i++)
        for(j=0; j<=n; j++)
            d[i][j]=inf;
    d[1][0]=0;
    for(i=1; i<=1<<n; i++)
        for(j=1; j<=n; j++)
            if(i&1<<j)
            {
                for(vector<int> ::iterator it=v[j].begin(); it!=v[j].end(); ++it)
                    if(i&(1<<*it))
                        d[i][j]=min(d[i][j],d[i^(1<<j)][*it]+cost[*it][j]);
                //minimul dintre costul de a ajunge din masca i in j (daca am mai ajuns vreodata) si
                //costul de a ajunge din masca i in *it si dupa in j prin *it
            }
     for(vector<int> ::iterator it=v[0].begin();it!=v[0].end();++it)
                s=min(s,d[(1<<n)-1][*it]+cost[*it][0]);
     if(s==inf)out<<"Nu exista solutie";
     else out<<s;

    return 0;
}