#include <bits/stdc++.h>
#define NMAX 100001
#define INF 0x3f3f3f3f3f3f3f3fLL  // INF mare pentru long long
#define mod 1000000007
using namespace std;


vector<vector<pair<int,int>>>graf(20);

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ifstream f("hamilton.in");
    ofstream g("hamilton.out");
    int n,m;
    f>>n>>m;
    for(int i=1; i<=m; ++i)
    {
        int x,y,c;
        f>>x>>y>>c;
        graf[y].push_back({x,c});
    }
    vector<vector<int>>dp(1<<n,vector<int>(n+1,1e9));
    dp[1][0]=0;
    for(int msk=3; msk<(1<<n); ++msk){
        for(int i=0; i<n; ++i)
            if(msk&(1<<i)){
                int new_msk=(msk^(1<<i));
            for(const auto& j : graf[i])
                if(new_msk&(1<<j.first))
                    dp[msk][i]=min(dp[msk][i],dp[new_msk][j.first]+j.second);
        }
    }
    int ans=1e9;
    for (const auto& it : graf[0])
      ans = min(ans, dp[(1 << n) - 1][it.first] + it.second);
   if (ans == 1e9)
      g << "Nu exista solutie\n";
   else
      g << ans << "\n";

    return 0;
}