#include <bits/stdc++.h>

using namespace std;

inline void Open(const string Name) {
    #ifndef ONLINE_JUDGE
        (void)!freopen((Name + ".in").c_str(), "r", stdin);
        (void)!freopen((Name + ".out").c_str(), "w", stdout);
    #endif
}

const int INF = 1e9;

vector <int> gr[19];

int dp[1 << 19][19], cost[19][19];
int N, M, x, y;

int calc(int conf, int last) {
    if(dp[conf][last] == -1) {
        dp[conf][last] = INF;

        for(int x : gr[last])
            if(conf & (1 << x)) {
                if(x == 0 && conf != (1 << last) + 1)
                    continue;

                dp[conf][last] = min(dp[conf][last], calc(conf ^ (1 << last), x) + cost[x][last]);
            }
    }

    return dp[conf][last];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    Open("hamilton");

    cin >> N >> M;
    for(int i = 0;i < N;i++)
        for(int j = 0;j < N;j++)
            cost[i][j] = INF;

    for(int i = 1;i <= M;i++) {
        cin >> x >> y;

        gr[y].emplace_back(x);
        cin >> cost[x][y];
    }

    memset(dp, -1, sizeof(dp));
    dp[1][0] = 0;

    int ans = INF;
    for(int x : gr[0])
        ans = min(ans, calc((1 << N) - 1, x) + cost[x][0]);

    cout << ans;


    return 0;
}