#include<fstream>
#include<list>
#include<climits>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const int NMAX=19,INF=18000000;
list<int>g[NMAX];
int cost[NMAX][NMAX],chain[1<<NMAX][NMAX],n,m;
void read_data(){
    fin>>n>>m;
    int from,to,c;
    while(m--){
        fin>>from>>to>>c;
        g[to].push_back(from);
        cost[from][to]=c;
    }
}
int minCost(){
    int mask,node;
    list<int>::iterator it;
    for(mask=0;mask<(1<<n);++mask)
        for(node=0;node<n;++node)
            chain[mask][node]=INF;
    chain[1][0]=0;
    for(mask=0;mask<(1<<n);++mask)
        for(node=0;node<n;++node)
            if(mask&(1<<node))
                for(it=g[node].begin();it!=g[node].end();++it)
                    if(mask&(1<<*it))
                        chain[mask][node]=min(chain[mask][node],chain[mask^(1<<node)][*it]+cost[*it][node]);
    int mincost=INF;
    for(it=g[0].begin();it!=g[0].end();++it)
        mincost=min(mincost,chain[(1<<n)-1][*it]+cost[*it][0]);
    return mincost;
}
int main(){
    read_data();
    fout<<minCost();
}