#include <iostream>
#include <fstream>
#include <vector>
#define oo 1<<30
#define Nmax 20
#define Cmax (1<<18)
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int N,M,dp[Cmax+5][Nmax],cost[Nmax][Nmax],sol=oo;
vector <int> G[Nmax];
void read()
{
    fin>>N>>M;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            cost[i][j]=oo;
    for(int i=1;i<=M;i++)
    {
        int x,y,c;
        fin>>x>>y>>c;
        G[y].push_back(x);
        cost[x][y]=c;
    }
}
void solve()
{
    int C=1<<N;
    for(int i=0;i<C;++i)
        for(int j=0;j<N;j++)
            dp[i][j]=oo;
    dp[1][0]=0;
    for(int i=0;i<C;++i)
        for(int j=0;j<N;++j)
            if(i&(1<<j))
                for(int k=0;k<G[j].size();++k)
                {
                    int nod=G[j][k];
                    if(i&(1<<nod))
                        dp[i][j]=min(dp[i][j],dp[i-(1<<j)][nod]+cost[nod][j]);
                }
    for(int i=0;i<G[0].size();++i)
        sol=min(sol,dp[C-1][G[0][i]]+cost[G[0][i]][0]);
    if(sol!=oo)
        fout<<sol<<"\n";
    else
        fout<<"Nu exista solutie\n";
}
int main()
{
    read();
    solve();
    return 0;
}