#include <fstream>
#include <vector>
#include <climits>

using namespace std;

ifstream fin ("hamilton.in");
ofstream fout ("hamilton.out");

const int NMAX = 18;
int cost[NMAX + 5][NMAX + 5];
vector <int> graph[NMAX + 5];

const int INF = 1e9;
int dp[1 << 18][NMAX + 2];

int main()
{
    int nodes , edges;
    fin >> nodes >> edges;

    for(int i = 0; i < nodes; i++)
        for(int j = 0; j < nodes; j++)
            cost[i][j] = INF;

    for(int i = 1; i <= edges; i++)
    {
        int node1 , node2 , cost_node;
        fin >> node1 >> node2 >> cost_node;

        graph[node1].push_back(node2);
        cost[node1][node2] = cost_node;
    }

    for(int i = 0; i < (1 << nodes); i++)
        for(int j = 0; j < nodes; j++)
            dp[i][j] = INF;
    dp[1][0] = 0;

    for(int config = 1; config <= (1 << nodes) - 1; config++)
    {
        for(int curr = 0; curr < nodes; curr++)
        {
            if(dp[config][curr] == INF)
                continue;

            for(auto neigh : graph[curr])
                dp[config | (1 << neigh)][neigh] = min(dp[config | (1 << neigh)][neigh] , dp[config][curr] + cost[curr][neigh]);
        }
    }

    int minim = INT_MAX;

    for(int i = 0; i < graph[0].size(); i++)
        minim = min(minim , dp[(1 << nodes) - 1][graph[0][i]] + cost[graph[0][i]][0]);

    fout << minim;

    fin.close();
    fout.close();
    return 0;
}