#include <bits/stdc++.h>

using namespace std;

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

#define pii pair<int, int>
#define pb push_back
#define fi first
#define se second

const int NMAX = 19;
const int INF = 0x3f3f3f3f;

int n, m, x, y, c, graf[NMAX][NMAX];
int dp[NMAX][1 << NMAX];

void read()
{
    in >> n >> m;
    while (m--)
        in >> x >> y >> c, graf[x][y] = c;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (!graf[i][j])
                graf[i][j] = INF;
}

void solve()
{
    // TSP

    memset(dp, INF, sizeof dp);

    for (int i = 0; i < n; i++)
        dp[i][1 << i] = graf[1][i];
    // we act as if the road from 1 to i is already counted, not from 0

    for (int mask = 0; mask <= (1 << n) - 1; mask++)
    {
        vector<int> from, to;
        for (int i=0; i<n; i++)
            mask & (1<<i) ?  from.pb(i) : to.pb(i);
        
        for (auto x : from)
            for (auto y : to)
                if (graf[x][y] != INF)
                    dp[y][mask | (1<<y)] = min(dp[y][mask | (1<<y)], dp[x][mask] + graf[x][y]);
                    //lasam masca asa cum e sau venim de la o masca cu ultimul nod x si ii adaugam muchia xy
        
    }

    //ajungem de unde am pornit, deci in 1
    out<<dp[1][(1<<n)-1];
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);

    read();
    solve();

    return 0;
}