#include <fstream>
#include <vector>

using namespace std;
ifstream cin("hamilton.in");
ofstream cout("hamilton.out");
int n,m;
vector<pair<int,int>> G[20];
vector<pair<int,int>> Gt[20];
int dp[18][1<<18];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,v;
        cin>>x>>y>>v;
        G[x].emplace_back(y,v);
        Gt[y].emplace_back(x,v);
    }
    for(int i=0;i<n;i++)
        for(int msk=0;msk<1<<n;msk++)
            dp[i][msk]=2e9;
    dp[0][1]=0;
    for(int msk=1;msk<1<<n;msk++)
    {
        for(int x=0;x<n;x++)
        {
            if(msk&(1<<x))
            {
                for(auto [y,v]:G[x])
                {
                    if(!(msk&(1<<y)))
                    {
                        dp[y][msk|(1<<y)]=min(dp[y][msk|(1<<y)],dp[x][msk]+v);
                    }
                }
            }
        }
    }
    int ans=2e9;
    for(auto [y,v]:Gt[0])
        ans=min(ans,dp[y][(1<<n)-1]+v);
    cout<<ans;
    return 0;
}