#include <fstream>
#include <vector>
#define sz 18
#define INF 0x3FFFFFFF
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int n,m;

int d[1<<sz + 1][sz + 1];

int v[sz+1][sz+1];

bool get_bit(int nr,int poz)
{
    return (nr>>poz)&1;
}

int main()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int c,x,y;
        fin>>x>>y>>c;
        v[x][y]=c;
    }
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<(1<<n); j++)
            d[j][i]=INF;
    }
    d[1][0]=0;

    for(int i = 1; i<(1<<n);i++)
        for(int j = 0;j<n;j++)
            if(get_bit(i,j) && d[i][j]!=INF){
                for(int x=0;x<n;x++)
                {
                    if(v[j][x]==0)
                        continue;
                    int vec = x;
                    int cost = v[j][x];
                    if(!get_bit(i,vec))
                        d[i + (1<<vec)][vec] = min(d[i + (1<<vec)][vec],d[i][j] + cost);
                }
            }
    int minim = INF;
    for(int i=0;i<n;i++)
        if(v[i][0]!=0)
            minim=min(minim,d[(1<<n)-1][i] + v[i][0]);
    if(minim!=INF)
        fout<<minim;
    else
        fout<<"Nu exista solutie";
}