#include <fstream>
#include <vector>
using namespace std;
#define MAXN 20
#define MAXX 262150
#define INF 100000000
int n, m, sol;
int cost[MAXN][MAXN];
int c[MAXX][MAXN];
vector <int> a[MAXN];
int main()
{
    ifstream in("hamilton.in");
    ofstream out("hamilton.out");
    int i,j,k,x,y;
    in>>n>>m;
    for(i=0;i<n;i++)
        for(j=0;j<n;++j)
            cost[i][j]=INF;
    for (i=0;i<m;i++)
    {
        in>>x>>y;
        a[y].push_back(x);
        in>>cost[x][y];
    }
    for(i=0;i<(1<<n);i++)
        for(j=0;j<n;j++) c[i][j]=INF;
    c[1][0]=0;
    for(i=0;i<(1<<n);i++)
        for(j=0;j<n;j++)
            if(i&(1<<j))
                for(k=0;k<a[j].size();k++)
                    if(i&(1<<a[j][k]))
                        c[i][j]=min(c[i][j],c[i^(1<<j)][a[j][k]] + cost[a[j][k]][j]);
    sol=INF;
    for(i=0;i<a[0].size();i++)
        sol=min(sol,c[(1<<n)-1][a[0][i]] + cost[a[0][i]][0]);
    if(sol==INF) out<<"Nu exista solutie"<<endl;
    else out<<sol<<endl;
    return 0;
}