#include <fstream>
#include <vector>

using namespace std;

const int INF = 1000000000;

vector<int> L[20];

int n,m,i,x,y,c,j,k,nod,Min;

int cost[20][20],d[20][1<<19];

int main() {
    ifstream f("hamilton.in");
    ofstream g("hamilton.out");
    f>>n>>m;
    for(i=1;i<=m;i++) {
        f>>x>>y>>c;
        L[x].push_back(y);
        cost[x][y]=c;
    }
    for(i=0;i<n;i++)
        for(j=0;j<=((1<<n)-1);j++)
            d[i][j]=INF;

    d[0][1]=0;
    for(j=1;j<(1<<n)-1;j++)
        for(i=0;i<n;i++)
            if(d[i][j]!=INF) {
                for(k=0;k<L[i].size();k++) {
                    nod=L[i][k];
                    if(((1<<nod)&j)==0)
                        d[nod][((1<<nod)|j)]=min(d[i][((1<<nod)|j)],d[i][j]+cost[i][nod]);
                }
            }
    Min=INF;
    for(i=1;i<n;i++)
            if(cost[i][0]!=0 && d[i][(1<<n)-1]+cost[i][0]<Min)
                Min=d[i][(1<<n)-1]+cost[i][0];

    if(Min!=INF)
        g<<Min<<"\n";
    else
        g<<"Nu exista solutie\n";
    return 0;
}