#include <iostream>
#include <fstream>
#define Nmax 19
#define Dim 1<<18
#define Max 20000000

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

int n, m, cost[Nmax][Nmax];
int dp[Dim][Nmax], sol=Max;

int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        f>>x>>y>>c;
        cost[x][y]=c;
    }
    for(int i=0;i<(1<<n);i++)
    {
        for(int j=0;j<n;j++)
            dp[i][j]=Max;
    }
    dp[1][0]=0;
    for(int i=0;i<(1<<n);i++)
    {
        for(int u=0;u<n;u++)
        {
            if((i&(1<<u))!=0)
            {
                for(int p=0;p<n;p++)
                {
                    if((i&(1<<p))!=0 && cost[p][u]!=0)
                    {
                        dp[i][u]=min(dp[i][u], dp[i^(1<<u)][p]+cost[p][u]);
                    }
                }
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        if(cost[i][0]!=0)
        sol=min(sol, dp[(1<<n)-1][i]+cost[i][0]);
    }
    if(sol==Max)
    {
        g<<"Nu exista solutie";
        return 0;
    }
    g<<sol;
    return 0;
}