#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#define pb push_back
#define mp make_pair
using namespace std;

vector<pair<int,int> > list[20],tmp;
vector<pair<int,int> >::iterator it;
int dp[20][(1<<18)+5];


int main()
{
    int n,m,rez=1<<30;
    ifstream f("hamilton.in");
    ofstream g("hamilton.out");
    f>>n>>m;
    memset(dp,127,sizeof(dp));
    for(;m;--m)
    {
        int a,b,c;
        f>>a>>b>>c;
        list[a].pb(mp(b,c));
        if(b==0)
            tmp.pb(mp(a,c));
        if(a==0)
            tmp.pb(mp(b,c));
    }
    dp[0][1]=0;
      for(int j=0;j<(1<<n);++j)
      {
         for(int i=0;i<n;++i)
         {
            for(it=list[i].begin();it!=list[i].end();++it)
            {
                int next_nod= it->first;
                int cost=it->second;
                if( ((1<<next_nod) & j)==0)
                {
                    dp[next_nod][ (1<<next_nod) | j]=min( dp[next_nod][ (1<<next_nod) | j] , dp[i][j] + cost );

                }
            }
          }
      }
    for(it=tmp.begin();it!=tmp.end();++it)
        rez=min(rez, dp[it->first][(1<<n)-1] + it->second);

    if(rez==1<<30)
        g<<"Nu exista solutie\n";
        else
            g<<rez;
    return 0;
}