#include <bits/stdc++.h>
#define db(x) cerr << #x <<":"<<x<<"  "
using namespace std;
#define x first
#define y second

const int N=20;

int n;
int st[N], v[N];
vector<pair<int,int>> g[N];
int cost, ans=1e9;

void backDfs(int k){
    int x=st[k-1];
    db(k);
    v[x]=1;
    for(auto [c,y]:g[x]){
        if(v[y]==0){
            st[k]=y; cost+=c;
            if(k==n){
                for(auto [c,z]:g[y]){
                    if(z==1){
                        ans=min(ans,cost+c);
                    }
                }
            }else
                backDfs(k+1);
            cost-=c;
        }
    }
    v[x]=0;
}

int32_t main(){
    cin.tie(0);
    cin.sync_with_stdio(0);
#ifndef ONLINE_JUDGE
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);
#endif

    int m;
    cin>>n>>m;
    for(int i=m; i--;){
        int x, y, c;
        cin>>x>>y>>c;
        g[x].push_back({c,y});
    }
    st[1]=1; v[1]=1;
    backDfs(2);
    cout<<ans;
}