#include <bits/stdc++.h>

using namespace std;

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

int n;
int m;
long long dp[20][270005];
struct el{
    int nod;
    int cost;
    int stare;
    bool operator < (const el &A) const{
        return cost>A.cost;
    }
};
struct  muchie
{
    int x;
    int cost;

};
priority_queue<el> Q;
vector <muchie> v[25];

int gaseste(int fiu , int st)
{

    if((st&(1<<(fiu-1)))>0)
        return 0;
    return 1;

}


void Dijkstra()
{
    while(!Q.empty())
    {
        int nod=Q.top().nod;
        int cost=Q.top().cost;
        int stare=Q.top().stare;

       /// cout<<nod<<" "<<cost<<" "<<stare<<"\n";
       /// cout<<nod<<" "<<cost<<" "<<stare<<"\n";


        for(int x=0;x<v[nod].size();++x)
        {

            int fiu=v[nod][x].x;
            int cc=v[nod][x].cost;

            if(gaseste(fiu , stare) && dp[nod][stare]+cc<dp[fiu][stare+(1<<(fiu-1))])
            {

                dp[fiu][stare+(1<<(fiu-1))]=dp[nod][stare]+cc;
                Q.push({fiu , cost+cc , stare+(1<<(fiu-1))});
            }
        }
        Q.pop();

    }

}



int main() {
    f>>n>>m;

    for(int i=1;i<=m;++i)
    {
        int prim,secund , co;
        f>>prim>>secund>>co;

        ++prim;
        ++secund;
        v[prim].push_back({secund , co});

    }
    int final=(1<<(n))-1;
    for(int i=0;i<=n;++i)
    {
        for(int j=0;j<=final+1;++j)
            dp[i][j]=INT_MAX;
    }
    Q.push({1 , 0 , 0});

    dp[1][0]=0;
    Dijkstra();

    if(dp[1][final]!=INT_MAX)
        g<<dp[1][final];
    else
        g<<"Nu exista solutie";



    return 0;
}