#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <map>
#include <iomanip>
#include <set>
#define x first
#define y second
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
const int MAXN = 20;
const int MAXX = 262150;
const int INF = 10000000;

int n, m, sol,i,j,a,b;
int cost[MAXN][MAXN];
int dp[MAXX][MAXN];
vector <int> v[MAXN];
int main()
{
    f>>n>>m;
    for(i=0;i<n;++i)
        for(j=0;j<n;++j)
            cost[i][j]=INF;
    for(i=1;i<=m;i++)
    {
        f>>a>>b;
        v[b].push_back(a);
        f>>cost[a][b];
    }
    for(i=0;i< (1<<n);++i)
        for(j=0;j<n;++j)
            dp[i][j]=INF;
    dp[1][0]=0;
    for(i=0;i< (1<<n);++i)
        for(j=0;j<n;++j)
            if(i&(1<<j))
                for(unsigned int q=0;q<v[j].size();++q)
                    if(i&(1<<v[j][q]))
                        dp[i][j]=min(dp[i][j],dp[i^(1<<j)][v[j][q]])+cost[v[j][q]][j];
    sol=INF;
    for(unsigned int i=0;i<v[0].size();++i)
        sol=min(sol,dp[(1<<n)-1][v[0][i]]+cost[v[0][i]][0]);
    if(sol==INF)    g<<"Nu exista solutie";
    else
        g<<sol;
    return 0;
}