#include <iostream>
#include <cstdio>
#define cout cerr
#define Max 20
#define MAX (1<<18)
#define INF 0x3f3f3f3f
using namespace std;

int dp[MAX][Max];
int cost[Max][Max];
int x,y,z,n,m;

void af_bi(int k)
{
    int nr=0,ass[100];
    while(k)
    {
        ass[nr++]=k%2;
        k/=2;
    }
    for(int i=6;i>nr;i--)
        cout<<0;
    for(int i=nr-1;i>=0;i--)
        cout<<ass[i];
}

int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);

    scanf("%d %d",&n,&m);


    for(int i=0; i<m; i++)
    {
        scanf("%d %d %d",&x,&y,&z);
        cost[x][y]=z;
    }
    for(int i=0; i<=(1<<n); i++)
        for(int j=0; j<n; j++)
            dp[i][j]=INF;
    for(int i=0; i<n; i++)
        if(cost[0][i]!=0)
            dp[(1<<(i-1))][i]=cost[0][i];


    for(int d=0; d<(1<<(n-1)); d++)
        for(int i=1; i<n; i++)
            if((d^(1<<(i-1)))<d)
                for(int v=1; v<n; v++)
                    if(cost[v][i]!=0)
                        dp[d][i]=min(dp[d][i],dp[(d^(1<<(i-1)))][v]+cost[v][i]);


    /*for(int i=0; i<(1<<(n-1)); i++,cout<<endl)
    {
        //cout<<i<<" ";
        af_bi(i);
        cout<<" -- ";
        for(int j=1; j<n; j++)
            if(dp[i][j]!=INF)
                cout<<dp[i][j]<<" ";
            else cout<<"~~ ";
    }*/

    int mini=INF;
    for(int i=1;i<n;i++)
        if(cost[i][0]!=0)
        mini=min(mini,dp[(1<<(n-1))-1][i]+cost[i][0]);
    /*for(int i=0;i<n;i++,cout<<endl)
        for(int j=0;j<n;j++)
        cout<<cost[i][j]<<" ";

    cout<<mini<<" ";

    cout<<dp[(1<<(n-1))-1][1];*/

    if(mini<INF)
        printf("%d",mini);
    else printf("Nu exista solutie");
    return 0;
}