#include <bits/stdc++.h>

using namespace std;

int cost[25][25];
int dp[(1<<18) + 1][25]; /// <mask, last_nod>
vector<pair<int, int>> adj[100005];

signed main()
{
    ifstream cin("hamilton.in");
    ofstream cout("hamilton.out");
    int n, m, a, b, val;
    cin>>n>>m;

    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cost[i][j] = 21e8;

    for(int i=0; i<m; i++)
    {
        cin>>a>>b>>val;
        cost[a][b] = val;

        adj[a].push_back({b, val});
    }

    for(int msk = 1; msk < (1<<n); msk ++)
        for(int j = 0; j < n; j ++)
            dp[msk][j] = 21e8;

    dp[1][0] = 0;

    for(int msk = 1; msk < (1<<n); msk ++)
    {
        for(int j = 0; j < n; j ++) /// nod
        {
            ///verificam daca nodu j e in mask

            if(msk & (1 << j) != 0)
                for(auto x : adj[j])
                {
                    int nod = x.first;
                    ///verificam ca nodu x sa NU fie in mask
                    if( (msk & (1 << nod)) == 0)
                    {
                        int new_msk = msk | (1 << nod);
                        dp[new_msk][nod] = min(dp[new_msk][nod], dp[msk][j]+ cost[j][nod]);
                    }
                }
        }
    }


    int minn = 21e8;
    for(auto x : adj[0]){
        int nod = x.first;
        if(dp[ (1 << n) - 1 ][nod] + cost[nod][0] < minn)
            minn = dp[ (1 << n) - 1 ][nod] + cost[nod][0];
    }

    if(minn == 21e8)
        cout<<"Nu exista solutie";
    else
        cout<<minn;

    return 0;
}