#include<fstream>
#include<iostream>
#include<vector>
#define inf 1e13
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
vector<vector<pair<int,int>>>revGraph;
const int NMAX1=19;
const int NMAX2=(1<<NMAX1)+1;
long long dp[NMAX2][NMAX1];

void setUp(){
    for(int i=0;i<NMAX2;++i){
        for(int j=0;j<NMAX1;++j){
            dp[i][j]=inf;   
        }
    }
}
int main(){
    setUp();
    int n,m;
    fin>>n>>m;
    int u,v,cost;
    revGraph.resize(n+1);
    for(int i=0;i<m;++i){
        fin>>u>>v>>cost;
        revGraph[v].push_back(make_pair(u,cost));
    }
    dp[1][1]=1;
    for(int mask=1;mask< (1 << n);++mask){
        for(int i=1;i<n;++i){
            if(!(mask&(1<<i))){ 
                for(auto vecin:revGraph[i]){
                    int vec=vecin.first;
                    int cost=vecin.second;
                    if(mask-(1<<vec)>=0 && dp[mask-(1<<vec)][vec]!=inf && (mask &(1<<vec))){
                    // cout<<"MIAU!!"<<endl;
                        dp[mask][i]=min(dp[mask][i],dp[mask-(1<<vec)][vec]+cost);
                    }
                }
            }
        }
    }
    long long fullMax=(1<<n)-1;//contine n elemente
    long long rez=inf;
    for(int i=1;i<n;++i){
        rez=min(rez,dp[fullMax-(1<<i)][i]);
    }
    fout<<rez*2;
    return 0;
}