#include <bits/stdc++.h>


using namespace std;

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

const short Nmax = 19;

const int Vmax = 1e9;

int dp[Nmax][(1 << (Nmax - 1)) + 1], n, m, cost[Nmax][Nmax];


struct Pair
{
    int nod, stare;
};

queue < Pair > Q;

int main()
{
    int x, y, c;
    Pair w;
    fin >> n >> m;
    for(int i = 0 ; i < n  ; i++)
        for(int j = 1 ; j <= (1 << n) - 1 ; j++)
            dp[i][j] = Vmax;
    for(int i = 0 ; i < n ; i++)
        for(int j = 0 ; j < n ; j++)
            cost[i][j] = Vmax;
    for(int i = 1 ; i <= m ; i++)
    {
        fin >> x >> y >> c;
        cost[x][y] = min(cost[x][y], c);
    }
    Q.push({0, 1});
    dp[0][1] = 0;
    while(!Q.empty())
    {
        w = Q.front();
        Q.pop();
        for(int i = 0 ; i < n ; i++)
        {
            if(cost[w.nod][i] == Vmax)
                continue;
            if(!(w.stare & (1 << i)) && dp[i][w.stare | (1 << i)] > dp[w.nod][w.stare] + cost[w.nod][i])
            {
                dp[i][w.stare | (1 << i)] =  dp[w.nod][w.stare] + cost[w.nod][i];
                Q.push({i, w.stare | (1 << i)});
            }
        }
    }
    cout << dp[3][9] << "\n";
    int ans = Vmax;
    for(int i = 1 ; i < n ; i++)
        ans = min(ans, dp[i][(1 << n) - 1] + cost[i][0]);
    fout << ans << "\n";
    fin.close();
    fout.close();
}