#include <iostream>
#include <fstream>
#include <vector>

const int MAXN = 18 + 1;

using namespace std;

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

vector<pair<int,int> >graf[MAXN];
/// dp[i][numar] inseamna costul minim de a ajunge din nodul 0 in nodul folosind nodurile marcate in numar cu bitii 1
/// dp[i][numar] = dp[j][ceva] + (1<<i)
int dp[MAXN][(1<<MAXN) + 5];
int n,m;

int main()
{
    in>>n>>m;
    for(int i = 1; i <= m; i++){
        int x,y,cost;
        in>>x>>y>>cost;
        graf[x].push_back({y,cost});
    }

    for(int i = 1; i <= n - 1; i++){
        for(int index = 0; index < graf[i].size(); index++){
            int vecin = graf[i][index].first;
            int cost = graf[i][index].second;
            for(int numar = 1; numar <= (1<<n); numar++){
                /// daca i se afla deja vizitat din dp[vecin][numar]
                if((numar & (1<<i)) > 0 || (dp[vecin][numar] == 0 && numar != (1<<j))
                    continue; /// nu e bun numar;
                dp[i][numar + (1<<i)] = min(dp[i][numar + (1<<i)],dp[vecin][numar] + cost);
            }
        }
    }
    return 0;
}