#include <fstream>
#include <vector>
#define NMAX 18
#define INF 2e9
using namespace std;

ifstream cin("hamilton.in");
ofstream cout("hamilton.out");

int cost[NMAX][NMAX],C[1 << NMAX][NMAX];
vector <int>Gt[NMAX];
int minim(int a, int b)
{
    if(a<b)
        return a;
    return b;
}

int main()
{
    int n,m,i,x,y,j,k,sol=INF;
    cin>>n>>m;
    for(i=0; i<n; i++)
        for(j=0; j<n; j++)
            cost[i][j]=INF;
    for(i=0; i< (1 << n); i++)
        for(j=0; j<n; j++)
            C[i][j]=INF;
    for(i=1; i<=m; i++)
    {
        cin>>x>>y;
        cin>>cost[x][y];
        Gt[y].push_back(x);
    }
    C[1][0]=0;
    for(j=1; j < (1 << n); j++)
        for(k=1; k<n; k++)
            for(vector <int>:: iterator it=Gt[k].begin(); it!=Gt[k].end(); it++)
                C[j][k]=minim(C[j][k],C[j ^ (1 << k)][*it]+cost[*it][k]);
    for(vector <int>::iterator it=Gt[0].begin();it!=Gt[0].end();it++)
        sol=minim(sol,C[(1 << n) -1][*it]+ cost[*it][0]);
    if(sol==INF)
        cout<<"Nu exista solutie";
    else
        cout<<sol;
    return 0;
}