#include <fstream>
#define DIM 18
#define INF 2000000001
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int n,m,x,y,cost,nr,mini,c[DIM][DIM],d[1<<DIM][DIM];
int main() {
    fin>>n>>m;
    while (m--) {
        fin>>x>>y>>cost;
        c[x][y]=cost;
    }
    nr=(1<<n)-1;
    for (int i=1;i<=nr;i++)
        for (int j=0;j<n;j++)
            d[i][j]=INF;
    d[1][0]=0;
    for (int st=1;st<=nr;st++)
        for (int i=0;i<n;i++)
            if ((st&(1<<i))!=0)
                for (int j=0;j<n;j++)
                    if (c[i][j]!=0 && (st&(1<<j))==0) {
                        int nxt=(st+(1<<j));
                        d[nxt][j]=min(d[nxt][j],d[st][i]+c[i][j]);
                    }
    mini=INF;
    for (int i=1;i<n;i++)
        if (c[i][0]!=0)
            mini=min(mini,d[nr][i]+c[i][0]);
    if (mini==INF)
        fout<<"Nu exista solutie";
    else
        fout<<mini;
    return 0;
}