#include <bits/stdc++.h>

using namespace std;

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

const long long bits_max=1<<18;

long long n, m, dp[20][bits_max];
long long cost[20][20], a, b, c;
long long bits_need;
void solve()
{

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

                for (long long 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]);
                    }
                }
            }
        }
    }
    long long maxi=0x3f3f3f3f;
    for (long long k=1; k<n; ++k)
    {
        if (cost[k][0]!=0x3f3f3f3f)
            maxi=min(maxi,dp[k][bits_need-1]+cost[k][0]);
    }
    g << maxi;
}

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