#include <bits/stdc++.h>

using namespace std;
ifstream in("hamilton.in");
ofstream out("hamilton.out");
const int nmax=18, inf=1e9;
int n, m;
vector <vector<int>> graph, dp;
int ciclu_hamiltonian()
{
    //nodurule de la 0 la n-1
    dp[1][0]=0;
    //dp[i][j]->drumul minim care se termina in j si are configuratia 1<<i
    for(int mask = 2; mask < (1<<n); mask++)
        if(mask&1)//contine nodul 0
        {
            for(int i=0; i<n; i++)
            {
                if(mask&(1<<i))//mask contine nodul i
                    for(int j=0; j<n; j++)
                    {
                        if(mask&(1<<j))//mask contine nodul j
                            dp[mask][i]=min(dp[mask][i], dp[mask^(1<<i)][j]+graph[j][i]);//minimul dintre ce e acum si ce era inainte sa fie si nodul i+distanta noua
                    }
            }
        }
    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()
{
    int x, y, c;
    in>>n>>m;
    graph.assign(n, vector<int>(n , inf));
    dp.assign(1<<n, vector<int>(n, inf));
    for(int i=1; i<=m; i++)
    {
        in>>x>>y>>c;
        graph[x][y]=c;
    }
    int rez=ciclu_hamiltonian();
    if(rez==-1)
    {
        out<<"Nu exista solutie";
    }
    else
        out<<rez;
}