#include <fstream>

using namespace std;
int n,m,p,C[19][19],dp[(1<<18)+5][19];
const int oo=2000000000;

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

void Read()
{
    int i,j,x,y,cost;
    in>>n>>m; p=1<<n;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            C[i][j]=oo;
    for(i=0;i<m;i++)
    {
        in>>x>>y>>cost;
        C[x][y]=cost;
    }
    for(i=0;i<p;i++)
        for(j=0;j<n;j++)
            dp[i][j]=oo;
    dp[1][0]=0;
}

void Solve()
{
    int i,j,k;
    for(i=1;i<p;i=i+2)
        for(j=1;j<n;j++)
            if(i&(1<<j))
            {
                for(k=0;k<n;k++)
                    if((i&(1<<k))&&k!=j)
                        dp[i][j]=min(1LL*dp[i][j],1LL*dp[i-(1<<j)][k]+C[k][j]);
            }
}

void Print()
{
    int sol=oo;
    for(int i=1;i<n;i++)
        sol=min(1LL*sol,1LL*dp[p-1][i]+C[i][0]);
    if(sol==oo)
        out<<"Nu exista solutie"<<'\n';
    else
        out<<sol<<'\n';
}

int main()
{
    Read();
    Solve();
    Print();
    return 0;
}