#include <bits/stdc++.h>

using namespace std;

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

const int bits_max=1<<18;

int n, m, dp[20][bits_max];
int cost[20][20], a, b, c;

void solve()
{
    int bits_need=(1<<n);
    for (int j=1; j<bits_need; ++j)
    {
        for (int i=0; i<n; ++i)
        {
            if (!((1<<i)&j))
                continue;
            else
            {

                for (int k=0; k<n; ++k)
                {
                    if (j&(1<<k) && cost[k][i]!=0x3f3f3f3f)
                    {
                        dp[i][j]=min(dp[i][j],dp[k][j^(1<<i)]+cost[k][i]);
                    }
                }
            }
        }
    }
    int maxi=0x3f3f3f3f;
    for (int k=1; k<n; ++k)
    {
        if (cost[0][k]!=0x3f3f3f3f)
            maxi=min(maxi,dp[0][bits_need-1]+cost[0][k]);
    }
    g << maxi;
}

int main()
{
    f >> n >> m;
    for (int i=0; i<n; ++i)
        for (int j=0; j<n; ++j)
            cost[i][j]=0x3f3f3f3f;
    for (int i=0; i<n; ++i)
    {
        for (int j=1; j<bits_max; ++j)
            dp[i][j]=0x3f3f3f3f;
    }
    for (int i=0; i<n; ++i)
        dp[i][1<<i]=0;
    for (int i=1; i<=m; ++i)
    {
        f >> a >> b >> c;
        cost[a][b]=c;
    }
    solve();
    return 0;
}