#include <fstream>
#include <vector>
using namespace std;
ifstream cin("hamilton.in");
ofstream cout("hamilton.out");


const int Inf = 0x3f3f3f3f;
vector<vector<int> > dp;
vector<vector<pair<int,int> > >sirad;
vector<int> pret;
int n,m,x,y,c;
int main()
{
    cin>>n>>m;
    sirad = vector<vector<pair<int,int> > >(n+1);
    dp = vector<vector<int> >((1<<n)+1,vector<int>(n+1,Inf));
    pret = vector<int>(n+1,Inf);
    while(m--)
    {
        cin>>x>>y>>c;
        sirad[x].push_back({y,c}); /// sir de adicenta invers
        if(y==0)
            pret[x] = c;
    }

    dp[1][0] = 0;


    for(int i=0;i<(1<<n);++i)
        for(int j=0;j<n;++j)
            if(i&(1<<j))
                for(auto k : sirad[j])
                    if(!(i&(1<<k.first)))dp[i|(1<<k.first)][k.first] = min(dp[i|(1<<j)][k.first], dp[i][j] + k.second);

    int res = Inf;
    for(int i=0;i<n;++i)
        res = min(res,dp[(1<<n)-1][i] + pret[i]);
    cout<<res;
    return 0;
}