#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

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

struct muchie{
    int nod;
    int cost;
};

const int N = 18;
const int INF = 0x3f3f3f3f;
vector <muchie> graph[N];
int dp[(1 << N + 1)][N];

int main(){
    int n, m;
    cin >> n >> m;
    memset(dp, INF, sizeof(dp));
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back({b, c});
    }
    dp[1][0] = 0;
    for (int config = 1; config < (1 << n); config++) {
        for(int nod = 0; nod < n; nod++){
            if(config & (1 << nod) and dp[config][nod] != INF) {
                for (auto vecin: graph[nod]) {
                    if (!(config & (1 << vecin.nod)))
                        dp[config | (1 << vecin.nod)][vecin.nod] = min(
                                dp[config | (1 << vecin.nod)][vecin.nod],
                                dp[config][nod] + vecin.cost);
                }
            }
        }
    }
    int config = (1 << n) - 1;
    int minim = INF;
    for (int nod = 1; nod < n; ++nod) {
        for(auto vecin : graph[nod]){
            if (vecin.nod == 0) {
                minim = min(dp[config][nod] + vecin.cost, minim);
            }
        }
    }
    if(minim == INF)
        cout << "Nu exista solutie";
    cout << minim;
    return 0;
}