#include <bits/stdc++.h>
#define oo 2e9
using namespace std;
ifstream in("hamilton.in");
ofstream out("hamilton.out");

int n, m, a[20][20];
int dp[20][1 << 18], N;
int main()
{
    int i, j, masca, x, y, cost;
    in >> n >> m;
    for(i = 1; i <= m; i++)
    {
        in >> x >> y >> cost;
        a[x][y] = cost;
    }
    N = (1 << n);
    for(i = 0; i < n; i++)
        for(j = 0; j < N; j++)
          dp[i][j] = oo;
    dp[0][1] = 0;
    for(masca = 3; masca < N; masca += 2)
        for(i = 0; i < n; i++)
           if(masca & (1 << i))
           {
               x = masca - (1 << i);
               for(j = 0; j < n; j++)
                if(x & (1 << j) and a[j][i])
                 dp[i][masca] = min(dp[i][masca], dp[j][x] + a[j][i]);
           }
    //for(i = 0; i < n; i++)
        //cout << dp[i][N - 1] << "\n";
    int sol = oo;
    for(i = 0; i < n; i++)
        if(a[i][0])
           sol = min(sol, dp[i][N - 1] + a[i][0]);
    out << sol << "\n";
    return 0;
}