#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream fin ("hamilton.in");
ofstream fout ("hamilton.out");

vector<int> graf[20];
int din[262150][20],cost[20][20];
const int INF=2000000000;

int main()
{
    int n,m;
    fin>>n>>m;
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++)
            cost[i][j]=INF;
    for (int i=0;i<m;i++)
    {
        int x,y,c;
        fin>>x>>y>>c;
        graf[y].push_back(x);
        cost[x][y]=c;
    }
    for (int masca=0;masca<(1<<n);masca++)
        for (int i=0;i<n;i++)
            din[masca][i]=INF;
    din[1][0]=0;
    for (int masca=0;masca<(1<<n);masca++)
        for (int i=0;i<n;i++)
            if (masca&(1<<i))
                for (int k=0;k<graf[i].size();k++)
                    if (masca&(1<<graf[i][k]))
                        din[masca][i] = min(din[masca][i], din[masca ^ (1<<i)][ graf[i][k] ] + cost[ graf[i][k] ][i]);
    int sol=INF;
    for (int i=0;i<graf[0].size();i++)
        sol=min(sol, din[(1<<n) - 1][ graf[0][i] ] + cost[ graf[0][i] ][0]);
    if (sol==INF)
        fout<<"Nu exista solutie\n";
    else
        fout<<sol<<'\n';
    return 0;
}