#include <bits/stdc++.h>

using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
#define cin fin
#define cout fout

int n,m,x,y,dp[1<<18][20],c,cost[20][20];
int main()
{
    cin>>n>>m;

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cost[i][j]=1e18;

    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>c;
        cost[x][y]=c;
    }

    int maximdp=(1<<n);

    for(int i=0;i<maximdp;i++)
        for(int j=0;j<n;j++)
            dp[i][j]=1e18;
    dp[1][0]=0;

    for(int mask=1;mask<maximdp;mask++)
        for(int i=0;i<n;i++)
        {
            if(dp[mask][i]==1e18) continue;

            for(int j=0;j<n;j++)
            {
                if(mask&(1<<j)) continue;
                if(cost[i][j]==1e18) continue;

                int nou=mask|(1<<j);

                dp[nou][j]=min(dp[nou][j],dp[mask][i]+cost[i][j]);
            }
        }

    int rez=1e18;

    for(int i=1;i<n;i++)
    {
        if(cost[i][0]==1e18)
            continue;

        rez=min(rez,dp[maximdp-1][i]+cost[i][0]);
    }

    if(rez==1e18) cout<<"Nu exista solutie";
    else cout<<rez;

    return 0;
}