#include <fstream>
#include <vector>


using namespace std;
#define inf 100000000
#define inf2 1<<20

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

int n,m,sol,i;
int cost[20][20];
int c[inf2][20];
int l;
vector <int> v[20];



void init()
{
    for (int i=0;i<l;i++)
        for (int j=0;j<n;j++)
         c[i][j]=inf;
}

void get_data()
{
    for (int i=0;i<m;i++)
    {
        int nod1,nod2;
        in>>nod1>>nod2;
        in>>cost[nod1][nod2];
        v[nod1].push_back(nod2);
    }
}

void solve()
{
    int i,j,k;
    for (i=0;i<l;i++)
        for (j=0;j<n;j++)
            if ( i & (1<<j) )

                for (k=0;k<v[j].size();k++)
                   {
                       int aux=v[j][k];

                       c[i^(1<<aux)][aux]=min(c[i^(1<<aux)][aux],c[i][j]+cost[j][aux]);
                   }






}
int main()
{
    in>>n>>m;
    l=1<<n;
    init();
    get_data();
    c[1][0]=0;
    solve();
    sol=inf;
    //cout<<cost[2][0]<<' ';
    for (i=0;i<n;i++)
        if (cost[i][0])
           {
               sol=min(sol,c[(1<<n)-1][i]+cost[i][0]);
             //  cout<<sol<<' ';
           }

    if (sol==inf) out<<"Nu exista solutie";
    else out<<sol;
    return 0;
}