#include <bits/stdc++.h>

using namespace std;
#define INF 1e9
ifstream f("hamilton.in");
ofstream g("hamilton.out");
vector <int> G[25];
int ad[20][20],n,m;
void read()
{
    int i,a,b,c;
    f>>n>>m;

        for(i=0;i<n;i++)
        for(a=0;a<n;a++)
    {
    if(a!=i)ad[i][a]=INF;
    }

    for(i=1;i<=m;i++)
    {
        f>>a>>b>>c;
        G[b].push_back(a);
        ad[a][b]=c;
    }



}
void afisare()
{
    int i;
    for(i=0;i<n;i++)
    {
        cout<<i<<":";
        for(auto x:G[i])
            cout<<x<<" ";
        cout<<endl;}
}
int main()
{
int i,mask;
read();
vector <vector <int> >  dp(n, vector <int> (1<<n,INF));
dp[0][1]=0;
for(mask=3;mask<(1<<(n));mask+=2)
{
    for(i=1;i<n;i++)
    {
        if((mask&(1<<i))!=0)
        {

            for(auto x:G[i]){
           if((mask&(1<<x))!=0) dp[i][mask]=min(dp[i][mask], dp[x][mask-(1<<i)] +ad[x][i]);}


        }
    }

}


int ans=INF;
mask=((1<<n)-1);
for(i=1;i<n;i++)
    ans=min(dp[i][mask]+ad[i][0],ans);
if(ans==INF) g<<"Nu exista solutie";
else g<<ans;


}