//#include <iostream>
#include <fstream>
#include <climits>
#include <cstring>
using namespace std;
ifstream cin("f.in");
ofstream cout("f.out");
int mask, cost[20][20], dp[1<<18][20], n, m, x, y, c;
int inf=999999999;
int tsp(int mask, int poz)
{
    if (mask==(1<<n)-1)
    {
        if (cost[poz][0]>0)
            return cost[poz][0];
        else return inf;
    }
    else if (dp[mask][poz]!=-1) return dp[mask][poz];
    int ans=inf;
    for (int i=0; i<n; i++)
        if (!(mask & (1<<i)) and cost[poz][i]>0)
            ans=min(ans, cost[poz][i]+tsp(mask | (1<<i), i));
    return dp[mask][poz]=ans;
}
int main()
{
    cin>>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++)
    {
        cin>>x>>y>>c;
        cost[x][y]=c;
    }
    memset (dp, -1, sizeof(dp));
    int sol=tsp(1, 0);
    if (sol==inf)
        cout<<"Nu exista solutie";
    else cout<<sol;
    return 0;
}