#include <fstream>
#include <vector>
using namespace std;
ifstream cin("hamilton.in");
ofstream cout("hamilton.out");


const int Inf = 0x3f3f3f3f;
vector<vector<int> > dp,pret;
vector<vector<int > >sirad;
int n,m,x,y,c;
int main()
{
    cin>>n>>m;
    sirad = vector<vector<int> >(n+1);
    dp = vector<vector<int> >((1<<n)+1,vector<int>(n+1,Inf));
    pret = vector<vector<int>>(n+1,vector<int>(n+1,Inf));
    while(m--)
    {
        cin>>x>>y>>c;
        sirad[x].push_back(y);
        pret[x][y] = c;
    }

    dp[1][0] = 0;


    for(int i=0;i<(1<<n);++i)
        for(int j=0;j<n;++j)
            if(i&(1<<j))
                for(auto k : sirad[j])
                    if(!(i&(1<<k)))dp[i|(1<<k)][k] = min(dp[i|(1<<j)][k], dp[i][j] + pret[j][k]);

    int res = Inf;
    for(int i=0;i<n;++i)
        res = min(res,dp[(1<<n)-1][i] + pret[i][0]);
    cout<<res;
    return 0;
}