#include <fstream>
#include <vector>

using namespace std;

ifstream cin ("hamilton.in");
ofstream cout ("hamilton.out");

const int INF = 1e9;

const int N = 18;
int dp[(1 << N) + 1][N + 1];

int c[N + 1][N + 1];

vector <pair <int, int> > gt[N + 1];

int n, m, x, y, cost;

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            c[i][j] = INF;
    for (int i = 1; i <= m; ++i)
    {
        cin >> x >> y >> cost;
        c[x][y] = cost;
        gt[y].push_back({x, cost});
    }
    for (int mask = 0; mask < (1 << n); ++ mask)
        for (int i = 0; i < n; ++i)
            dp[mask][i] = INF;
    dp[1][0] = 0;
    for (int mask = 2; mask < (1 << n); ++mask)
        for (int i = 0; i < n; ++i)
            if ((1 << i) & mask)
                for (auto it : gt[i])
                    dp[mask][i] = min (dp[mask][i], dp[mask ^ (1 << i)][it.first] + it.second);
    int ans = INF;
    for (int i = 1; i < n; ++i)
        if (c[i][0] != INF)
            ans = min (ans, dp[(1 << n) - 1][i] + c[i][0]);
    cout << ans << '\n';
    return 0;
}