#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <iomanip>
#include <cmath>
#define inf 123456789
using namespace std;

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

int dp[(1<<19)+5][20],c[20][20],cost,x,y,i,j,k,N,M;

vector<int> v[25];

int main()
{
    f>>N>>M;
    for (i=1;i<1<<N;++i)
        for(j=0;j<N;++j)
            dp[i][j]=inf;

    for(i=0;i<N;++i)
        for(j=0;j<N;++j)
            c[i][j]=inf;


    for (i=1;i<=M;++i)
    {
        f>>x>>y>>cost;
        c[y][x]=cost;
        v[y].push_back(x);
    }

    dp[1][0]=0;

    for(i=1;i<1<<N;++i)
        for (j=0;j<N;++j)
            if (i & (1<<j))
                for(k=0;k<N;++k)
                    {
                        dp[i][j]=min(dp[i][j],dp[i^(1<<j)][k] + c[k][j]);
                    }
    int rasp = inf;
    for(i=1;i<N;++i)
        if (dp[(1<<N)-1][i] + c[i][0] < rasp)
            rasp = dp[(1<<N)-1][i] + c[i][0];

    g<<rasp;


    return 0;
}