#include <iostream>
#include <fstream>
#define INF 1000000000

using namespace std;

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

int n,m,cost[18][18],d[300000][18],minim;

int main()
{
    int i,j,k,p,q,r;
    in>>n>>m;
    for(i=0;i<n;++i)
    {
        for(j=0;j<n;++j)
            cost[i][j]=INF;
    }
    for(i=1;i<=m;++i)
    {
        in>>p>>q>>r;
        cost[p][q]=r;
    }
    for(i=1;i<(1<<n);++i)
    {
        for(j=0;j<n;++j)
            d[i][j]=INF;
    }
    d[1][0]=0;
    for(i=2;i<(1<<n);++i)
    {
        for(j=0;(1<<j)<=i;++j)
        {
            if((i&(1<<j))==(1<<j))
            {
                for(k=0;(1<<k)<=i;++k)
                {
                    if((i&(1<<k))==(1<<k) && j!=k)
                    {
                        if(d[i][j]>d[i^(1<<j)][k]+cost[k][j])
                            d[i][j]=d[i^(1<<j)][k]+cost[k][j];
                    }
                }
            }
        }
    }
    minim=INF;
    for(j=1;j<n;++j)
    {
        if(d[(1<<n)-1][j]+cost[j][0]<minim)
        {
            minim=d[(1<<n)-1][j]+cost[j][0];
        }
    }
    if(minim!=INF)
        out<<minim;
    else
        out<<"Nu exista solutie";
    return 0;
}