#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

vector <int> v[20];
const int INF = 1000000000;
int n, m, C[20][20], D[262146][20];
int main()
{
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);
    scanf("%d%d", &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){
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        C[x][y] = c;
        v[y].push_back(x);
    }
    for(int i = 0; i < 1 << n ; ++i)
        for(int j = 0; j < n ; ++j) D[i][j] = INF;
    D[1][0] = 0;
    for(int i = 0; i < 1 << n ; ++i){
        for(int j = 0; j < n ; ++j){
            if(i & (1 << j)){
                for(vector <int> :: iterator it = v[j].begin() ; it != v[j].end() ; ++it){
                    if(i & (1 << *it))
                        D[i][j] = min(D[i][j], D[i ^ (1 << j)][*it] + C[*it][j]);
                }
            }
        }
    }
    int Sol = INF;
    for(vector <int> :: iterator it = v[0].begin() ; it != v[0].end() ; ++it)
        Sol = min(Sol, D[(1 << n) - 1][*it] + C[*it][0]);
    printf("%d", Sol);
    return 0;
}