#include <bits/stdc++.h>
#define ull unsigned long long
#define FILES freopen("hamilton.in","r",stdin);\
              freopen("hamilton.out","w",stdout);
#define CMAX 1000000
#define fastio std::ios_base::sync_with_stdio(NULL),cin.tie(NULL),cout.tie(NULL);
#define mp make_pair
#define INF 999999999999999
#define void inline void
#define mod 1000000007
#define ll long long
#define MAX 100
#define SMAX 10000
#define pb push_back
#define add emplace_back
using namespace std;
int dp[262149][20],n,m,mask;
vector<pair<int,int>> v[MAX+5];
void bfs(int x)
{
    queue<pair<int,int>> q;
    q.push(mp(x,0));
    while(!q.empty())
    {
        x = q.front().first;
        int y = q.front().second;
        for(auto i : v[x])
        {
            if(y & (1 << (i.first-1))) continue;
            int u = (y ^ (1<<(i.first-1)));
            if(dp[u][i.first] > dp[y][x] + i.second)
            {
                q.push(mp(i.first,u));
                dp[u][i.first] = dp[y][x] + i.second;
            }
        }
        q.pop();
    }
}
int main()
{
   fastio
   FILES
   cin >> n >> m;
   mask = (1<<n)-1;
   for(int i = 1;i <= m; ++i)
   {
       int a,b,c;
       cin >> a >> b >> c;
       a++,b++;
       v[a].add(mp(b,c));
   }
       for(int j = 1;j <= n; ++j)
           for(int k = 1;k <= mask; ++k) dp[k][j] = 1e9;
    int best = 1e9;
    for(int i = 1;i <= n; ++i)
    {
        bfs(i);
        best = min(best,dp[mask][i]);
        for(int j = 1;j <= n; ++j)
           for(int k = 1;k <= mask; ++k) dp[k][j] = 1e9;
    }
    cout << best;
}