#include <cstdio>
#include <vector>
#define MAXX 10000000
using namespace std;
int dyn[262150][20];
int drum[20];
bool vis[262150][20];
vector<int> adj[20],cst[20];
int n,m;
int minim(int a,int b)
{
    if(a<b) return a;
    return b;    
}
int main()
{
    freopen ("hamilton.in","r",stdin);
    freopen ("hamilton.out","w",stdout);
    scanf("%d%d",&n,&m);
    int x1,x2,c;
    for(int i=1;i<=m;i++)
    {
            scanf("%d%d%d",&x1,&x2,&c);
            adj[x1].push_back(x2);
            cst[x1].push_back(c);
            if(x2==0) drum[x1]=c;
    }
    vis[1][0]=1;
    int LIM=(1<<n);
    for(int i=0;i<LIM;i++)
    {
            for(int j=0;j<=n;j++) dyn[i][j]=MAXX;
    }
    dyn[1][0]=0;
    for(int i=1;i<LIM;i++)
    {
            for(int j=0;j<n;j++)
            {
                    if(vis[i][j]==1)
                    {
                                    vector<int>::iterator it1,it2;
                                    for(it1=adj[j].begin(),it2=cst[j].begin();it1!=adj[j].end();++it1,++it2)
                                    {
                                         if(!(i&(1<<*it1))&&dyn[i|(1<<*it1)][*it1]>dyn[i][j]+*it2)
                                         {
                                                                                  vis[i|(1<<*it1)][*it1]=1;
                                                                                  dyn[i|(1<<*it1)][*it1]=dyn[i][j]+*it2;
                                         }
                                    }
                    }
            }
    }
    int minim=MAXX;
    for(int i=1;i<n;i++)
    {
            if(drum[i]!=0) minim=min(minim,drum[i]+dyn[LIM-1][i]);
    }
    printf("%d\n",minim);
}