#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
#pragma GCC target("avx,avx2,fma")

using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

const int NMAX=18,PMAX=(1<<18);
int n,m,i,j,k,stare,dp[PMAX+5][NMAX+5],c[NMAX+5][NMAX+5],node1,node2,cost,E[PMAX+5],v[NMAX+5],nr,sol=1e9;
vector <int> adj[NMAX+5];
int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr); fout.tie(nullptr);

    fin>>n>>m;

    if (n==1)
    {
        fout<<0;
        return 0;
    }

    for (int i=2; i<=PMAX; i++)
        E[i]=E[i>>1]+1;

    while (m--)
    {
        fin>>node1>>node2>>cost;
        adj[node1].push_back(node2);
        c[node1][node2]=cost;
    }

    for (int i=0; i<(1<<n); i++)
        for (int j=0; j<n; j++)
            dp[i][j]=1e9;

    dp[1][0]=0;

    for (stare=1; stare<(1<<n); stare++)
    {
        int val=(stare)&(stare-1);

        if (val!=0)
        {
            int auxstare=stare;
            nr=0;

            while (auxstare)
            {
                int lsb=(auxstare)&(-auxstare),e=E[lsb];
                v[++nr]=e;
                auxstare-=lsb;
            }

            for (int i=1; i<=nr; i++)
            {
                node1=v[i];
                for (auto node2: adj[node1])
                {
                    int val2=(stare)&(1<<node2);

                    if (val2!=0)
                        dp[stare][node2]=min(dp[stare][node2],c[node1][node2]+dp[stare-(1<<node2)][node1]);
                }
            }
        }
    }

    stare=(1<<n)-1;

        for (j=1; j<n; j++)
            if (c[j][0]!=0)
                sol=min(sol,dp[stare][j]+c[j][0]);


    if (sol==1e9)
        fout<<"Nu exista solutie";
    else
        fout<<sol;

    return 0;
}