#include <fstream>
#include <math.h>

using namespace std;
ifstream in("hamilton.in");
ofstream out("hamilton.out");
const int N = 20, inf = 2e9;

int n, m, dp[1<<18][N], a[N][N];

int main()
{
    in >> n >> m;
    for(int i=1; i<=m; i++) {
        int x, y, c;
        in >> x >> y >> c;
        a[x][y] = c;
    }

    dp[1][0] = 1;
    for(int j=2; j<(1<<n); j++) {
        int pw = 1, cnt = 0;
        while(pw <= j) {
            if(j & pw) {
                int mask = j ^ pw;
                if(mask) {
                    dp[j][cnt] = inf;
                    for(int i=0; i<n; i++)
                        if(a[i][cnt] && dp[mask][i])
                            dp[j][cnt] = min(dp[j][cnt], dp[mask][i] + a[i][cnt]);
                }
            }

            pw *= 2;
            cnt++;
        }
    }

    int ans = inf;
    for(int i=0; i<n; i++)
        if(dp[(1<<n)-1][i] && a[i][0])
            ans = min(ans, dp[(1<<n)-1][i] + a[i][0]);

    out << ans - 1;
    return 0;
}