#include <fstream>
#include <vector>
using namespace std;
ifstream cin("hamilton.in");
ofstream cout("hamilton.out");
const int MaxS = 1<<18,MaxN = 19,Inf= 0x3f3f3f3f;

int C[MaxS][MaxN];
vector<int> G[MaxN];
int w[MaxN][MaxN];
int n,m,x,y,c;
int main()
{
    cin>>n>>m;

    for(int i=0;i<n;++i)
        for(int j=0;j<=n;++j)
            w[i][j] = Inf;

    for(int i=1;i<=m;++i)
    {
        cin>>x>>y>>c;
        G[x].push_back(y);
        w[x][y] = c;
    }


    for(int mask = 0; mask< 1<<n; ++mask)
        for(int i = 0 ;i<n;++i)
            C[mask][i] = Inf;
    C[1][0] = 0;


    for(int i=0;i<(1<<n);++i)
        for(int j=0;j<n;++j)
            if(i&(1<<j))
                for(auto k : G[j])
                    if(!(i&(1<<k)))
                        C[i |(1<<k)][k] = min(C[i|(1<<k)][k], C[i][j] + w[j][k]);

    int res = Inf;
    for(int i=0;i<n;++i)
        res = min(res,C[(1<<n)-1][i] + w[i][0]);
    if(res==Inf)
        cout<<"Nu exista solutie\n";
    else cout<<res<<'\n';
    return 0;
}