#include <bits/stdc++.h>
#define INF 342000010
using namespace std;
int n,m,i,j,c[30][30],dp[300000][30],a,no,mi,x,y;
vector<int>v[30];
int main()
{
    ifstream f ("hamilton.in");
    ofstream g ("hamilton.out");
    f>>n>>m;
    for(i=0; i<=20; ++i)
        for(j=0; j<=20; ++j)
            c[i][j]=INF;
    for(i=1; i<=m; ++i)
    {
        f>>x>>y;
        f>>c[x][y];
        v[x].push_back(y);
    }
    for(i=0; i<=(1<<n); ++i)
        for(j=0; j<=n; ++j)
            dp[i][j]=INF;
    dp[1][0]=0;
    for(i=1; i<(1<<n); ++i)
        for(j=0; j<n; ++j)
        {
            if (dp[i][j]==INF) continue;
            for (auto &it : v[j])
            {
                a=it;
                if((1<<a)&i)continue;
                no=(i|(1<<a));
                dp[no][a]=min(dp[no][a],dp[i][j]+c[j][a]);
                ++a;
            }
        }
    no = (1<<n)-1, mi=INF;
    for(j=0; j<n; ++j)
        mi=min(mi,dp[no][j]+c[j][0]);
    if (mi==INF)g<<"Nu exista solutie"<<'\n';
    else g<<mi<<'\n';
    return 0;
}