#include <bits/stdc++.h>
#define ull unsigned long long
#define FILES freopen("rec.in","r",stdin);\
              freopen("rec.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[MAX+5][MAX+5][MAX+5],n,m,mask;
vector<pair<int,int>> v[MAX+5];
void bfs(int x)
{
    queue<pair<int,int>> q;
    q.push(mp(x,0));
    int s = x;
    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[s][u][i.first] > dp[s][y][x] + i.second)
            {
                q.push(mp(i.first,u));
                dp[s][u][i.first] = dp[s][y][x] + i.second;
            }
        }
        q.pop();
    }
}
int main()
{
   fastio
   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 i = 1;i <= n; ++i)
       for(int j = 1;j <= n; ++j)
           for(int k = 1;k <= (1 << n); ++k) dp[i][k][j] = 1e9;
    for(int i = 1;i <= n; ++i) bfs(i);
    int best = 1e9;
    for(int i = 1;i <= n; ++i) best = min(best,dp[i][mask][i]);
    cout << best;
}