#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int INF=999999999,n,m,cost[20][20],dp[1<<18][20],x,y,c;
int tsp(int mask, int pos)
{
    if(mask == (1<<n)-1)
    {
        if(cost[pos][0]>0)
            return cost[pos][0];
        else return INF;
    }
    else if(dp[mask][pos] != -1)return dp[mask][pos];

    int ans=INF;
    for(int i=0;i<n;i++)
        if(!(mask & (1<<i)) and cost[pos][i]>0)
            ans=min(ans, cost[pos][i]+tsp(mask | (1<<i), i));
    return dp[mask][pos]=ans;
}
int main()
{
    fin>>n>>m;
    memset(cost, 0, sizeof(cost));
    for(int i=1;i<=n;i++)
        cost[i][i]=-1;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        cost[x][y]=c;
    }
    memset(dp, -1, sizeof(dp));
    int sol= tsp(1,0);
    if(sol==INF)
        fout<<"Nu exista solutie";
    else fout<<sol;
    return 0;
}