#include <fstream>
#include <vector>

using namespace std;

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

int cost[20][20];//costul muchiei din a in b
int dp[600001][19];//costul minim ai sa fi trecut prin toate nodurile aferente bitilor setati din config unde last e poz min
int n,m;

vector<int>g[19];

int build_dp()
{
    int start = 0;
    dp[1<<start][start] = 0;
    for(int config = 1; config <= (1<<n)-1; config++)// config e bitmaskul in care nodul i se afla in traseu daca nodul i este setat
        for(int curr = 0; curr < n; curr++)//dp[config][curr] nu exista..nu am pb pt ca infinit
            for(int index = 0; index < g[curr].size(); index++)//vecinii elem curr
            {
                int vecin = g[curr][index];
                if((config & (1<<vecin)) == 0)
                    dp[config | (1<<vecin)][vecin] = min(dp[config | (1<<vecin)][vecin], dp[config][curr] + cost[curr][vecin]);
            }

    int config = (1 << n) - 1;// 2^0 + 2^1 + ... + 2^n ///am trecut prin toate nodurile

    int ciclumin = 1e9;
    for(int last = 1; last < n; last++)
    {
        if(cost[last][0] != 0)
            ciclumin = min(ciclumin, (dp[config][last] + cost[last][0]) );
    }

    return ciclumin;

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

        g[x].push_back(y);

        cost[x][y] = price;

    }

    for(int i = 0; i < (1<<n); i++)
        for(int j = 0; j < n; j++)
            dp[i][j] = 1e9;

    out<<build_dp();

    return 0;
}