#include <fstream>
#include <algorithm>
#include <iomanip>
#include <vector>

#define pdd pair<double, double>
#define INF (1 << 30)
#define x first
#define y second
#define mkp make_pair
#define nMax 20
#define pb push_back
#define MOD 666013
#define confMax (1 << 18)
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int n, m;
int C[confMax][nMax], Cost[nMax][nMax];
vector<int> G[nMax];
void read()
{
    int a, b, c;
    fin>>n>>m;

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            Cost[i][j]=INF;

    for(int i=0;i<(1 << n);i++)
        for(int j=0;j<n;j++)
            C[i][j]=-1;

    for(int i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        G[b].pb(a);
        Cost[a][b]=c;
    }

    C[1][0]=0;
}
int memo(int conf, int last)
{
    if(C[conf][last]==-1)
    {
        C[conf][last]=INF;
        for(vector<int>::iterator it=G[last].begin();it!=G[last].end();it++)
        {
            int fiu=*it;
            if(conf & (1 << fiu))
            {
                if(fiu==0 && conf!=(1 << last)+1)
                    continue;
                C[conf][last]=min(C[conf][last], memo((conf ^ (1 << last)), fiu)+Cost[fiu][last]);
            }
        }
    }
    return C[conf][last];
}
void solve()
{
    int Sol=INF;

    for(vector<int>::iterator it=G[0].begin();it!=G[0].end();it++)
    {
        int fiu=*it;
        Sol=min(Sol, memo((1 << n)-1, fiu) + Cost[fiu][0]);
    }

    Sol==INF ? fout<<"Nu exista solutie" : fout<<Sol;
}
int main()
{
    read();
    solve();
    return 0;
}