#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f ("hamilton.in");
ofstream g ("hamilton.out");
int n,m;
vector<pair<int,int>>adiacenta[20];
int dp[1<<18][19];
void init()
{
    for(int i = 0;i<(1<<18);i++)
    {
        for(int j = 0;j<=18;j++)
        {
            dp[i][j] = (1<<30)-1;
        }
    }
    for(int i = 0;i<n;i++)
        dp[1<<i][i] = 0;
}
void citire()
{
    f >> n >> m;
    for(int i = 1;i<=m;i++)
    {
        int x,y,c;
        f >> x >> y >> c;
        adiacenta[x].push_back({y,c});
    }
}
void dp1()
{
    for(int masca = 1;masca<(1<<n);masca++)
    {
        for(int nod = 0;nod<n;nod++)
        {
            if((masca&(1<<nod)) != 0)
            {
                for(auto x:adiacenta[nod])
                {
                    int nod_vecin = x.first;
                    int cost_vecin = x.second;
                    if((masca&(1<<nod_vecin))!=0)
                    {
                        dp[masca][nod_vecin] = min(dp[masca][nod_vecin],dp[masca^(1<<nod_vecin)][nod]+cost_vecin);
                    }
                }
            }
        }
    }
    int rasp_min = (1<<30)-1;
    for(int i= 1;i<=n;i++)
    {
        for(auto x:adiacenta[i])
        {
            if(x.first == 0)
            {
                rasp_min = min(rasp_min,x.second+dp[(1<<n)-1][i]);
            }
        }
    }
    g << rasp_min;
}
int main()
{
    citire();
    init();
    dp1();
}