#include <fstream>
#include <vector>
#include <limits.h>
#define pb push_back
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const int INF=1e7;
vector<pair<int,int>> adj[20];
int dp[(1 << 19)][20];

int main()
{
    int n, m;
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        fin >> a >> b >> c;
        adj[b].pb({a, c});
    }
    for (int i = 0; i < (1 << n); i++)
    {
        for (int j = 0; j < n; j++)
            dp[i][j] = INF;
    }
    dp[1][0]=0;

    for(int msk=1;msk<(1<<n);msk++)
    {
        for(int i=0;i<n;i++)
        {
            if(msk & (1<<i))
            {
                int prev_msk=(msk^(1<<i));
                if(prev_msk==0)
                continue;
               for(auto j:adj[i])
               {
                if(prev_msk & (1<<j.first))
                dp[msk][i]=min(1LL*dp[msk][i],1LL*dp[(prev_msk)][j.first]+j.second);
               }
            }
        }
    }

    int rez=INF;

    for(int i=0;i<n;i++)
    {
        rez=min(1LL*rez,1LL*dp[(1<<n)-1][i]+adj[i][0].second);
    }
    fout<<rez;

}