#include <fstream>
#include <vector>

using namespace std;
ifstream in("hamilton.in");
ofstream out("hamilton.out");
const int N=20;
const int INF=1<<30;
vector<int>a[N];
int n,m,cost[N][N],d[1<<N][N];//d[i][j]=lantul de cost minim de la 0 la j care contine nodurile ce corespund cu 1 in config binara a lui i

int main()
{
    int x,y,c;
    in>>n>>m;
    for(int i=0;i<(1<<n);i++)
        for(int j=0;j<n;j++)
            d[i][j]=INF;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cost[i][j]=INF;
    for(int i=1;i<=m;i++)
    {
        in>>x>>y>>c;
        cost[x][y]=c;
        a[y].push_back(x);
    }
    for(int i=1;i<(1<<n);i++)
        for(int j=1;j<n;j++)
            if(i&(1<<j))
                for(unsigned k=0;k<a[j].size();k++)
                    if(i&(1<<a[j][k]))
                        d[i][j]=min(d[i][j],d[i-(1<<j)][a[j][k]]+cost[a[j][k]][j]);
    int sol=INF;
    for(unsigned k=0;k<a[0].size();k++)
        sol=min(sol,d[(1<<n)-1][a[0][k]]+cost[a[0][k]][0]);
    if(sol==INF)
        out<<"Nu exista solutie";
    else
        out<<sol;
    return 0;
}