#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
const int maxn=22;
const int inf=1<<30;
vector <int> G[maxn];
int N,M;
int Cost[maxn][maxn];
int C[100000][maxn];
int main()
{
    int i,j,x,y,z,sz,k,next,ans;
    f>>N>>M;
    for (i = 0; i < N; ++i)
        for (j = 0; j < N; ++j) Cost[i][j] = inf;

    for (i = 0; i < 1 << N; ++i)
        for (j = 0; j < N; ++j) C[i][j] = inf;
    for (i=1;i<=M;i++)
    {
        f>>x>>y>>z;
        G[y].push_back(x);
        Cost[x][y]=z;
    }
    C[1][0]=0;
    for (i=0;i< 1 << N;i++)
    {
        for (j=0;j<N;j++)
            if (i & (1<<j))
            {
                cout<<i<<" "<<j<<endl;
                sz=G[j].size();
                for (k=0;k<sz;k++)
                {
                    next=G[j][k];
                    if ((i & (1<<next))&&Cost[next][j]!=inf)
                        C[i][j] = min(C[i][j], C[i ^ (1<<j)][ next ] + Cost[ next ][j]);
                }
            }
    }
    ans=inf;

    for (i=0; i<G[0].size();i++)
        {
            if (Cost[ G[0][i] ][0]==inf) continue;
            ans = min(ans, C[(1<<N) - 1][ G[0][i] ] + Cost[ G[0][i] ][0]);

        }
    if (ans == inf) g<<"Nu exista solutie"<<endl;
    else g<<ans;

    return 0;
}