#include <fstream>
#include <vector>

#define INF 0x3f3f3f3f
#define nMax 18
#define bitMax 262150
#define pb push_back

using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int n, m, Cost[nMax][nMax], C[bitMax][nMax], Sol;
vector<int> G[nMax];
void read()
{
    int x, y, z;
    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]=INF;
    C[1][0]=0;

    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>z;
        G[y].pb(x);
        Cost[x][y]=z;
    }
}
void solve()
{
    for(int i=0;i < (1 << n);i++)
    {
        for(int j=0;j<n;j++)
        {
            if(i & (1 << j))
            {
                for(vector<int>::iterator it=G[j].begin();it!=G[j].end();it++)
                {
                    int fiu=*it;
                    if(i & (1 << fiu))
                        C[i][j]=min(C[i][j], C[i ^ (1 << j)][fiu] + Cost[fiu][j]);
                }
            }
        }
    }
    Sol=INF;
    for(vector<int>::iterator it=G[0].begin();it!=G[0].end();it++)
    {
        int fiu=*it;
        Sol=min(Sol, C[(1 << n)-1][fiu]+Cost[fiu][0]);
    }
    if(Sol==INF)
        fout<<"Nu exista solutie";
    else
        fout<<Sol;
}
int main()
{
    read();
    solve();
    return 0;
}