#include <fstream>

using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int n,m,mat[20][20],cost[20][20],doi[21],dp[262150][22];
int main()
{
    doi[0]=1;
    for(int i=1;i<=18;i++)
        doi[i]=doi[i-1]*2;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        fin>>x>>y;
        mat[x][y]=1;
        fin>>cost[x][y];
    }
    for(int i=1;i<n;i++)
    {
        if(mat[0][i])
            dp[(1<<i)|1][i]=cost[0][i];
    }
    for(int mask=2;mask<=doi[n]-1;mask++)
    {
        for(int y=1;y<n;y++)
            if(mask&(1<<y))
            {
                int mask1=mask^(1<<y),minim=100000000;
                for(int x=1;x<n;x++)
                {
                    if(mask1&(1<<x))
                    {
                        if(mat[x][y])
                            minim=min(minim,dp[mask1][x]+cost[x][y]);
                    }
                }
                if(dp[mask][y]==0)
                    dp[mask][y]=minim;
            }
    }
    int minim=100000000;
    for(int i=1;i<n;i++)
    {
        if(mat[i][0])
           minim=min(minim,dp[doi[n]-1][i]+cost[i][0]);
    }
    fout<<minim;
    return 0;
}