#include <bits/stdc++.h>
using namespace std;
ifstream fin ("hamilton.in");
ofstream fout ("hamilton.out");
int n, m, dp[(1<<19)+5][20];
vector<pair<int,int>> v[20], r[20];
void read();
int main()
{
    read();
    for(int cnf=1; cnf<=(1<<n)-1; ++cnf)
        for(int i=0; i<n; i++)
            dp[cnf][i] = INT_MAX;
    dp[1][0] = 0;
    for(int cnf=3; cnf<=(1<<n)-1; cnf+=2)
    {
        for(int i=1; i<n; i++)
            if((cnf&(1<<i)))
            {
                int mask = (cnf^(1<<i));
                for(auto it:r[i])
                    if(dp[mask][it.first] != INT_MAX)
                        dp[cnf][i] = min(dp[cnf][i], dp[mask][it.first] + it.second);
            }
    }
    int minn = INT_MAX, cnf = (1<<n)-1;
    for(int i=1; i<n; i++)
        for(auto it:v[i])
            if(it.first == 0)
            {
                minn = min(minn, dp[cnf][i] + it.second);
                //break;
            }
    fout << minn;
    return 0;
}
void read()
{
    fin >> n >> m;
    for(int i=1; i<=m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        v[x].push_back(pair<int,int>(y, c));
        r[y].push_back(pair<int,int>(x, c));
    }
}