#include <bits/stdc++.h>
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int dp[400009][22], fv[1009];
struct elem
{
    int nod, cost;
};
vector <elem> v[25];
signed main ()
{
    int n, m;
    f >> n >> m;
    for (int i=1; i<=m; i++)
    {
        int x, y, z;
        f >> x >>y >> z;
        x++, y++;
        fv[x*30+y]=z;
        v[x].push_back({y,z});
    }
    for (int i=0; i<=(1<<n); i++)
        for (int j=0; j<=n; j++)
            dp[i][j]=1e9;
    dp[1][1]=0;
    for (int stare=1; stare<=(1<<n)-1; stare++)
    {
        for (int nodx=1; nodx<=n; nodx++)
        {
            int p=(1<<(nodx-1));
            //cout << p << ' ';
            if (stare&p)
            {
                for (int nody=1; nody<=n; nody++)
                {
                    if (fv[nodx*30+nody])
                    {
                        //cout << nodx << ' ' << nody <<'\n';
                        int p2=(1<<(nody-1));
                        if ((stare&p2)==0) dp[(stare|p2)][nody]=min (dp[stare|p2][nody], dp[stare][nodx]+fv[nodx*30+nody]);
                    }
                }
            }
        }
    }
    int minim=1e9, sf=(1<<n)-1;
    for (int i=2; i<=n; i++)
    {
        if (fv[i*30+1])
            minim=min(minim, dp[sf][i]+fv[i*30+1]);
    }
    if (minim!=1e9) g << minim;
    else g << "Nu exista solutie";
}