#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>

#define Nmax 19
#define INF 0x3f3f3f3f

using namespace std;

int DP[1<<Nmax][Nmax];
vector<pair<int,int> > G[Nmax];
int N,M;

void Read(){
    scanf("%d%d",&N,&M);
    int a,b,c;
    for(int i = 1; i <= M; ++i){
        scanf("%d%d%d",&a,&b,&c);
        G[b].push_back(make_pair(c,a));
    }
}

void Solve()
{
    memset(DP,INF,sizeof(DP));

    DP[1][0] = 0; /// plecam din nodul 0

    int lim = (1<<N) - 1;
    for(int MASK = 0; MASK <= lim; ++MASK)
        for(int i = 0; i < N; ++i)
            if(MASK & (1<<i)) /// exista bit-ul in mask
                for(vector<pair<int,int> >::iterator it = G[i].begin(); it != G[i].end(); ++it)/// vedem de unde putem veni (graful transpus)
                    if(MASK & (1<<it->second)) /// daca e in mask si locul de unde am venit
                        if(DP[MASK][i] > DP[MASK ^(1<<i)][it->second] + it->first)
                            DP[MASK][i] = DP[MASK ^(1<<i)][it->second] + it->first;

    int best = INF;
    for(vector<pair<int,int> >::iterator it = G[0].begin(); it != G[0].end(); ++it) /// vedem de unde putem ajunge in nodul 0
        if(best > DP[lim][it->second] + it->first)
            best = DP[lim][it->second] + it->first;
    printf("%d\n",best);
}

int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);

    Read();
    Solve();

    return 0;
}