#include <fstream>
#include <algorithm>
#include <cstring>

#define DIM 17
#define INF 0x3f3f3f3f
#define F(value) (value+1)>>1

/**

                .,aadd"'    `"bbaa,.
            ,ad8888P'          `Y8888ba,
         ,a88888888              88888888a,
       a88888888888              88888888888a
     a8888888888888b,          ,d8888888888888a
    d8888888888888888b,_    _,d8888888888888888b
   d88888888888888888888888888888888888888888888b
  d8888888888888888888888888888888888888888888888b
 I888888888888888888888888888888888888888888888888I
,88888888888888888888888888888888888888888888888888,
I8888888888888888PY8888888PY88888888888888888888888I
8888888888888888"  "88888"  "88888888888888888888888
8::::::::::::::'    `:::'    `:::::::::::::::::::::8
Ib:::::::::::"        "        `::::::' `:::::::::dI
`8888888888P            Y88888888888P     Y88888888'
 Ib:::::::'              `:::::::::'       `:::::dI
  Yb::::"                  ":::::"           "::dP
   Y88P                      Y8P               `P
    Y'                        "
                                `:::::::::::;8"
       "888888888888888888888888888888888888"
         `"8;::::::::::::::::::::::::::;8"'
            `"Ya;::::::::::::::::::;aP"'
                ``""YYbbaaaaddPP""''
**/

using namespace std;

int N,M,X,Y,Z,minim,temp_mask,V[(1<<DIM)+2],temp_mask2,v1,v2,D[(1<<DIM)+2][DIM+1],C[DIM+1][DIM+1];

class parser{
    public:
        parser() {}
        parser(const char *file_name){
            input_file.open(file_name,ios::in | ios::binary);
            input_file.sync_with_stdio(false);
            index=0;
            input_file.read(buffer,SIZE);}
        inline parser &operator >>(int &n){
            for (;buffer[index]<'0' or buffer[index]>'9';inc());
            n=0;
            for (;'0'<=buffer[index] and buffer[index]<='9';inc())
                n=10*n+buffer[index]-'0';
            return *this;}
        ~parser(){
            input_file.close();}
    private:
        fstream input_file;
        static const int SIZE=0x400000;
        char buffer[SIZE];
        int index=0;
        inline void inc(){
            if(++index==SIZE)
                index=0,input_file.read(buffer,SIZE);}
};

parser f ("hamilton.in");

int main (){
    ofstream t ("hamilton.out");
    memset(C,INF,sizeof(C));
    memset(D,INF,sizeof(D));
    f>>N>>M;
    for(int i=1;i<=M;++i){
        f>>X>>Y>>Z;
        C[X][Y]=Z;
    }
    for(int i=0;i<=DIM;++i)
        V[1<<i]=i;
    D[1][0]=0;
    for(int mask=3;mask<1<<N;mask+=2){
        temp_mask=mask;
        while(temp_mask){
            v1=V[temp_mask&(-temp_mask)];
            temp_mask-=temp_mask&(-temp_mask);
            if(v1==0) continue;
            else{
                temp_mask2=mask-(1<<v1);
                while(temp_mask2){
                    v2=V[temp_mask2&(-temp_mask2)];
                    temp_mask2-=temp_mask2&(-temp_mask2);
                    D[F(mask)][v1]=min(D[F(mask)][v1],D[F(mask-(1<<v1))][v2]+C[v2][v1]);
                }
            }
        }
    }
    minim=INF;
    for(int i=0;i<N;++i)
        minim=min(minim,D[F((1<<N)-1)][i]+C[i][0]);
    if(minim==INF)
        t<<"Nu exista solutie\n";
    else
        t<<minim;
    return 0;
}