#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;
        }
        bool operator<(const Edge&e)const{
            return e.c<c;
        }
};
vector<Edge>g[N+1],h[N+1];
int d[1<<18+1][19];
int n,m;
void DP(){
    int i,j,i1;
    int father=0,S,p=1<<n;
    for(i=0;i<p;i++)
        for(j=0;j<n;j++){
            if(i%1<<(j+1)>=i<<j){
                int minD=INF+1;
                for(i1=0;i1<h[j].size();i1++)
                    minD=min(minD,d[i^(1<<j)][h[j][i1].v]+h[j][i1].c);
                d[i][j]=minD;
            }
            else
                d[i][j]=INF+1;
        }
}
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));
    }
    DP();
    int i1,minD=INF+1,p=(1<<n)-1;
    for(i1=0;i1<h[0].size();i1++)
        minD=min(minD,d[p][h[0][i1].v]+h[0][i1].c);
    printf("%d",minD);
    return 0;
}