#include <fstream>

using namespace std;
int dp[(1<<20)][20],c[20][20];
const int inf=1<<30;

void solve()
{
    ifstream cin("hamilton.in");
    ofstream cout("hamilton.out");
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(i!=j)
               c[i][j]=inf;
        }
    }
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        cin>>c[a][b];
    }
    for(int i=0;i<(1<<n);i++)
    {
        for(int j=0;j<n ;j++)
            dp[i][j]=inf;
    }
    dp[1][0]=0;
    for(int i=1;i<(1<<n);i+=2)
    {
        for(int j=0;j<n;j++)
        {
            if(((1<<j) & i))
            {
                for(int k=0;k<n;k++)
                {
                    if(!((1<<k) & i) && c[j][k]!=inf)
                       dp[i | (1<<k)][k]=min(dp[i | (1<<k)][k],dp[i][j]+c[j][k]);
                }
            }
        }
    }
    int ans=inf;
    for(int i=1;i<n;i++)
        {
            if(c[i][0]!=inf)
               ans=min(ans,dp[(1<<n)-1][i]+c[i][0]);
        }
    if(ans!=inf)
       cout<<ans;
    else
        cout<<"Nu exista solutie";
}

int main()
{
    solve();
    return 0;
}