#include <bits/stdc++.h>

using namespace std;

ifstream f("hamilton.in");
ofstream g("hamilton.out");
const int oo = 1000000000;
int n,m;
int main()
{
    f>>n>>m;
    vector<vector<int>> c(n,vector<int>(n,oo));
    for(; m; m--)
    {
        int x,y,z;
        f>>x>>y>>z;
        c[x][y]=z;
    }

    n--;
    int Mask=1<<n;
    vector<vector<int>> dp(Mask,vector<int>(n,oo));
    for(int i=0; i<n; i++)
        dp[1<<i][i]=c[n][i];
    Mask--;
    for(m=1; m<Mask; m++)
    {
        vector<int> S,D;
        for(int i=0,j=1; i<n; i++,j<<=1)
            if(m&j)
                S.push_back(i);
            else
                D.push_back(i);
        for(auto s:S)
            for(auto d:D)
                dp[m|(1<<d)][d]=min(dp[m|(1<<d)][d],dp[m][s]+c[s][d]);
    }
    int sol=oo;
    for(int i=0;i<n;i++)
        sol=min(sol,dp[Mask][i]+c[i][n]);
    g<<sol;
    return 0;
}