#include <bits/stdc++.h>

#define NMax 19
#define INF (1 << 30) - 1
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");

int n,m,x,y,c;
int preLog[(1 << 18)];
int a[NMax][NMax];
int best[(1 << 18)][NMax][NMax];

int main()
{
    f >> n >> m;
    for(int i = 0; i <= n; ++i){
        for(int j = 0; j <= n; ++j){
            if(i != j)
                a[i][j] = INF;
        }
    }
    for(int i = 1; i <= m; ++i){
        f >> x >> y >> c;
        a[x][y] = c;
    }
    for(int mask = 0; mask <= (1 << n); ++ mask)
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < n; ++j)
                best[mask][i][j] = INF;

    for(int i = 0; i < n; ++i){
        best[(1 << i)][i][i] = 0;
    }
    for(int mask = 0; mask <= (1 << n); ++ mask){

        for(int i = 0; i < n; ++i){

            for(int j = 0; j < n; ++j){

                for(int start = 0; start < n; ++ start){
                    if(!(mask & (1 << j)) && a[i][j] != INF && i != j){
                        best[mask|(1 << j)][j][start] = min(best[mask|(1 << j)][j][start],best[mask][i][start] + a[i][j]);
                    }
                }
            }
        }
    }

    int ans = INF;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            ans = min(ans,best[(1 << n) - 1][i][j] + a[i][j]);
        }
    }
    g << ans << '\n';
    return 0;
}