///dp[i][j], costul minim de a ajunge in nodul i cu masca j de noduri parcursa

#include <fstream>
#include <vector>

using namespace std;

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

const int INF = 1e9;

using pa = pair <int, int>;

const int N = 18;
const int M = (1 << N);

int dp[M + 1][N + 1], f[N + 1][N + 1];

vector <pa> gt[N + 1];

int n, m, x, y, cost;

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        cin >> x >> y >> cost;
        f[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 = 1; 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 mn = INF;
    for (int i = 1; i < n; ++i)
        if (f[i][0])
        mn = min (mn, dp[(1 << n) - 1][i] + f[i][0]);
    cout << mn << '\n';
    return 0;
}