#include <bits/stdc++.h>

using namespace std;

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

int n,m,x,y,c,cost[20][20],dp[300000][20];

int main()
{
    f>>n>>m;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cost[i][j]=INT_MAX;
    for(int i=1; i<=m; i++)
        f>>x>>y>>c, cost[x][y]=c;

    int valmax=(1<<n)-1;
    for(int mask=1; mask<=valmax; mask++)
        for(int i=0; i<n; i++)
            dp[mask][i]=INT_MAX;
    dp[1][0]=0;
    for(int mask=1; mask<=valmax; mask++)
    {
        for(int i=0; i<n; i++)
            if(mask&(1<<i) and dp[mask][i]!=INT_MAX)
            {
                for(int j=0; j<n; j++)
                    if((mask&(1<<j))==0 and cost[i][j]!=INT_MAX)
                    {
                        int newmask=mask|(1<<j);
                        dp[newmask][j]=min(dp[newmask][j], dp[mask][i]+cost[i][j]);
                    }
            }
    }
    int minim=INT_MAX;
    for(int i=0; i<n; i++)
        if(dp[valmax][i]!=INT_MAX and cost[i][0]!=INT_MAX)
            minim=min(minim, dp[valmax][i]+cost[i][0]);
    g<<minim;
    return 0;
}