#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define ll long long
#define ull unsigned long long
#define ld long double
#define chad char
#define mod 666013
#define dim 100005
#define lim 1000000
#define BASE 31
#define NMAX 21'005
#define FOR(i,a,b) for(int i=(a); i<=(b); i++)
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define nr_biti __builtin_popcount
using namespace __gnu_pbds; 
using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int n,m;
vector<pii> gt[18];
int dp[(1<<18)][18];
bool mem[(1<<18)][18];
int to0[18];

int search(int mask,int nod)
{
    if(mem[mask][nod])
        return dp[mask][nod];

    mem[mask][nod]=1;
    dp[mask][nod]=INT_MAX;

    for(auto it:gt[nod])
    {
        if(mask&(1<<it.first))
        {
            int u=search(mask^(1<<nod),it.first);
            if(u==INT_MAX)
                continue;

            dp[mask][nod]=min(dp[mask][nod],u+it.second);
        }
    }
    return dp[mask][nod];
}

int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);

    fin >> n >> m;
    for(int i=1; i<=m; i++)
    {
        int a,b,w;
        fin >> a >> b >> w;
        gt[b].pb(mp(a,w));

        if(b==0)
            to0[a]=w;
    }

    int ans=INT_MAX;
    mem[1][0]=1;
    dp[1][0]=0;

    for(int i=0; i<n; i++)
    {   
        int u=search((1<<n)-1,i);
        if(u!=INT_MAX && (to0[i]!=0 || i==0))
            ans=min(ans,u+to0[i]);
    }

    if(ans==INT_MAX)
        fout << "Nu exista solutie";
    else 
        fout << ans;

    return 0;
}