#include <iostream>
#include <cstdio>
#include <vector>
#include <utility>
#include <climits>
#include <algorithm>
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,1e8));
    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]==1e8)return rez;
    i=0;
    msk=pn-2;
    ll mn;
    rez.pb(0);
    while(msk!=0)
    {
        mn=-1;
        for(j=0;j<n;j++)
        {
            if(!((1<<j)&msk))continue;
            //cerr<<j<<' '<<dp[msk][j]<<' '<<adi[j][i]<<endl;
            if(mn==-1||(dp[msk][j]+adi[j][i])<(dp[msk][mn]+adi[mn][i]))mn=j;
        }
        i=mn;
        msk-=(1<<i);
        rez.pb(i);
    }
    rez.pb(0);
    reverse(rez.begin(),rez.end());
    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,1e8));
    for(i=0;i<m;i++)
    {
        cin>>a>>b>>c;
        adi[a][b]=c;
    }
    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;
}