#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream cin ("hamilton.in");
ofstream cout ("hamilton.out");
int dp[18][1<<18];
vector< pair<int,int> > g[20];
int n;
int m;
int calc (int vf,int masca)
{
    if (dp[vf][masca]==-1)
    {
        dp[vf][masca] = 2e9;
        for (auto mch:g[vf])
        {
            int x = mch.first;
            if ((1<<x)&masca)
                dp[vf][masca] = min(dp[vf][masca],calc(x,masca^(1<<vf))+mch.second);
        }
    }
    return dp[vf][masca];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i=1; i<=m; i++)
    {
        int x,y,c;
        cin >> x >> y >> c;
        g[x].push_back({y,c});
    }
    for(int i=0; i<n; i++)
        for(int j=0; j<(1<<n); j++)
            dp[i][j] = -1;
    int rasp = 2e9;
    dp[0][1<<0] = 0;
    for (auto mch:g[0])
        rasp = min(rasp, calc(mch.first,(1<<n)-1) + mch.second);
    if(rasp == 2e9)
    {
        cout << "Nu exista solutie";
        return 0;
    }
    cout << rasp;
    return 0;
}