#include<bits/stdc++.h>
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
const int INF=0x3F3F3F3F;
int n,m,ans;
vector<vector<int>>graph,dp;
int hamilton()
{
    dp.assign((1<<n),vector<int>(n,INF));
    dp[1][0]=0;

    for(int mask=2; mask<(int)dp.size();mask++)
        if(mask&1)
            for(int i=0;i<n;i++)
                if(mask&(1<<i))
                    for(int j=0;j<n;j++)
                        if(mask&(1<<j))
                            dp[mask][i]=min(dp[mask][i],dp[mask^(1<<i)][j]+graph[j][i]);
    int ans=INF;
    for(int i=0;i<n;i++)
        ans=min(ans,dp[(1<<n)-1][i]+graph[i][0]);
    if(ans==INF)
        return -1;
    return ans;
}
int main()
{
    f>>n>>m;
    graph.assign(n,vector<int>(n,INF));
    for(int i=1,x,y,c;i<=m;i++)
    {
        f>>x>>y>>c;
        graph[x][y]=c;
    }
    ans=hamilton();
    if(ans==-1)
        g<<"Nu exista solutie";
    else
        g<<ans;
    return 0;
}