#include <iostream>
#include <cstdio>
#include <vector>
#include <utility>
#include <climits>
using namespace std;
#define pb(x) push_back(x)
#define fir first
#define sec second
typedef int ll;
typedef pair<ll,ll> pll;
vector<ll> MCHC(vector<vector<ll>> adi)
{
    // nodurile se indexeaza de la 0
    vector<ll> rez;
    ll n=adi.size(),pn=(1<<n),msk,i,j,k;
    vector<vector<ll>> dp(pn,vector<ll>(n,INT_MAX));
    for(i=1;i<n;i++)
        dp[1<<i][i]=adi[0][i];
    for(msk=1;msk<pn;msk++)
    {
        for(i=1;i<n;i++)
        {
            if(!((1<<i)&msk))continue;
            for(j=0;j<n;j++)
            {
                if((1<<j)&msk)continue;
                dp[msk+(1<<j)][j]=min(dp[msk+(1<<j)][j],dp[msk][i]+adi[i][j]);
            }
        }
    }
    if(dp[pn-1][0]==INT_MAX)return cout<<"Nu exista solutie",rez;
    cout<<dp[pn-1][0]<<endl;
    //daca rez e gol atunci nu exista ciclu
    // ciclul incepe de la 0
    return rez;
}
int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n,m,i,j,a,b,c;
    cin>>n>>m;
    vector<vector<ll>> adi(n,vector<ll>(n,INT_MAX));
    for(i=0;i<m;i++)
    {
        cin>>a>>b>>c;
        adi[a][b]=c;
    }
    MCHC(adi);
    /*vector<ll> rez=MCHC(adi);
    if(rez.empty())
        return cout<<"Nu exista solutie",0;
    ll srez=0;
    for(ll i=1;i<rez.size();i++)srez+=adi[rez[i-1]][rez[i]];
    cout<<srez<<'\n';*/
	return 0;
}