#include<cstdio>
#include<vector>
using namespace std;
const int INF=20000000,N=18;
class Edge{
    public:
        int v,c;
        Edge(){
        }
        Edge(int vv,int cc){
            v=vv;
            c=cc;
        }
};
vector<Edge>g[N+1],h[N+1];
int d[(1<<18)+1][19];
int n,m;
int DP(int p,int node){
    if(d[p][node]>0)
        return d[p][node];
    int i;
    if(node==0)
        return 0;
    int minD=INF+1;
    for(i=0;i<h[node].size();i++){
        Edge son=h[node][i];
        if(son.v==0&&p!=(1<<node)+1)
            continue;
        int pp=1<<son.v;
        if((p/pp)%2==1)
            minD=min(minD,DP(p-(1<<node),son.v)+son.c);
    }
    d[p][node]=minD;
    return minD;
}
int main(){
    int x,y,z,i;
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d%dm",&x,&y,&z);
        g[x].push_back(Edge(y,z));
        h[y].push_back(Edge(x,z));
    }
    int i1,minD=INF+1,p=(1<<n)-1;
    for(i1=0;i1<h[0].size();i1++)
        minD=min(minD,DP(p,h[0][i1].v)+h[0][i1].c);
    printf("%d",minD);
    return 0;
}