#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <vector>
#include <string.h>
#include <limits.h>

using namespace std;

int n,m;

vector<int> a[20];

//2^18 = 262144
int c[262150][20];
int cost[20][20];

int calculate(int conf, int lastNode){

    if (c[conf][lastNode] == -1){
        c[conf][lastNode] = INT_MAX;

        for (int i=0; i<a[lastNode].size(); i++){
            int newNode = a[lastNode][i];
            if ((conf & (1 << newNode)) != 0){
                //if only the current last and the 0 node is not yet visited

                if (newNode == 0){
                    if (conf == ((1 << lastNode) + 1)){
                        c[conf][lastNode] = cost[newNode][lastNode];
                        break;
                    } else {
                        continue;
                    }
                }
                else {
                    int newValue = calculate(conf ^ (1 << lastNode), newNode);
                    if (newValue != INT_MAX){
                        c[conf][lastNode] = min(c[conf][lastNode], newValue + cost[newNode][lastNode]);
                    }
                }
            }

        }
    }

    return c[conf][lastNode];
}

int main()
{
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);

    scanf("%d %d", &n, &m);

    int from, to, edgeCost;
    for (int i=0; i<m; i++){
        scanf("%d %d %d", &from, &to, &edgeCost);
        cost[from][to] = edgeCost;
        a[to].push_back(from);
    }

    memset(c, -1, sizeof(c));


    c[1][0] = 0;
    int minn = INT_MAX;
    int lastNode;

    for (int i=0; i<a[0].size(); i++){
        lastNode = a[0][i];
        int calculatedValue = calculate((1 << n) - 1, lastNode);

        if (calculatedValue != INT_MAX){
            minn = min(minn, calculatedValue + cost[lastNode][0]);
        }
    }

    printf("%d", minn);

    return 0;
}