#include <fstream>
#include <vector>

using namespace std;

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

const int inf = 500000000;
int N, M;
vector <int> G[20], D[20];
int dp[18][(1 << 18)]; //dp[i][j] - costul minim de a ajunge in nodul i, avand starea j

int main()
{
    f >> N >> M;
    for (int i = 1; i <= M; ++i)
    {
        int x, y, c;
        f >> x >> y >> c;
        G[x].push_back(y);
        D[x].push_back(c);
    }

    for (int i = 0; i < N; ++i)
        for (int s = 1; s < (1 << N); ++s)
            dp[i][s] = inf;
    dp[0][1] = 0;
    for (int s = 1; s < (1 << N); ++s)
        for (int i = 0; i < N; ++i)
            if (s & (1 << i))
                for (int j = 0; j < G[i].size(); ++j)
                    if ((s & (1 << G[i][j])) == 0)
                        dp[j][(s + (1 << G[i][j]))] = min(dp[j][(s + (1 << G[i][j]))], dp[i][s] + D[i][j]);
    int ans = inf;
    for (int i = 1; i < N; ++i)
    {
        int find_ciclu = -1;
        for (int j = 0; j < G[i].size(); ++j)
            if (G[i][j] == 0)
                find_ciclu = j;
        if (find_ciclu != -1)
            ans = min(ans, dp[i][(1 << N) - 1] + D[i][find_ciclu]);
    }
    g << ans;
    f.close();
    g.close();
    return 0;
}