#include <bits/stdc++.h>

using namespace std;
ifstream in("hamilton.in");
ofstream out("hamilton.out");
const int NMAX = 20;
const int inf = 0x3f3f3f3f;
struct Radu{
    int next, costmuchie;
};
vector <Radu> g[NMAX];
int dp[(1<<18) + 1][NMAX];
int edge[NMAX][NMAX];
int main()
{
    memset(dp, inf, sizeof(dp));
    int n, m;
    in >> n >> m;
    for( int i = 0; i < m; i++ ){
        int a, b, c;
        in >> a >> b >> c;
        g[a].push_back({b, c});
        edge[a][b] = c;
    }
    dp[1][0] = 0;
    for( int config = 1; config < (1 << n); config++ ){
        for( int curnode = 0; curnode < n; curnode++ ){
            if( ( config & (1 << curnode)) == 0 || dp[config][curnode] == inf )
               continue;
            for( int i = 0; i < g[curnode].size(); i++ ){
                int nxtNode = g[curnode][i].next;
                if( (config & (1 << nxtNode )) == 0 )
                    dp[config | (1 << nxtNode )][nxtNode] = min( dp[config | (1 << nxtNode )][nxtNode], 
                        dp[config][curnode] + g[curnode][i].costmuchie);
            }
        }
    }
    int rez = inf;
    int config = (1<<n) -1;
    for( int curnode = 1; curnode < n; curnode++ ){
        if( edge[curnode][0] )
            rez = min( rez, dp[config][curnode] + edge[curnode][0] );
    }
    out << rez;
    return 0;
}