#include <fstream>
#include <limits>

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

struct branch{
    int node, cost;
};

constexpr int N = 18;
constexpr int LIM = 1 << N;
constexpr int INF = 1e9;
int n, m;
long long dp[LIM][N]; // costul minim al unui drum elementar care incepe in 0, contine toate varfurile din submultimea 
                     // codificata de i(in binar), si se termina pe varful j(care apartine multimii reprezentate de i)
long long cost[N][N];

long long getRes(){
    int mask = (1 << n) - 1;
    long long res=INF;
    for(int j=1; j<n; ++j){
        if(cost[j][0] == INF) continue;
        res = std::min(res, dp[mask][j] + cost[j][0]);
        out << res << '\n';
    }
    return res;
}

int main (){
    in >> n >> m;
    for(int i=0; i<n; ++i){
        std::fill(cost[i], cost[i] + n, INF);
        cost[i][i] = 0;
    }
    for(int i=0; i<m; ++i){
        int u, v, c;
        in >> u >> v >> c;
        cost[u][v] = c;
    }
    int lim = 1 << n;
    for(int i=0; i<lim; ++i)
        std::fill(dp[i], dp[i] + n, INF);
    dp[1][0] = 0;
    for(int mask=1; mask<lim; mask += 2){
        for(int node=0; node<n; ++node){
            if ((1 << node) & mask){///j apartine i, deci are sens dp[i][j]{
                for (int succ=0; succ<n; succ++){
                    if (!((1 << succ) & mask) && cost[node][succ] != INF){///k e un succesor al lui j{
                        int newMask = (mask | (1 << succ));
                        dp[newMask][succ] = std::min(dp[newMask][succ], dp[mask][node] + cost[node][succ]);
                        //out << dp[newMask][succ] << '\n';
                    }
                }
            }
        }
    }
    out << getRes();
}