/*dp[mask][i] - costul minim al unui lant care incepe in 
nodul 0 parcurge toate
nodurile din mask si se termina in nodul i

dp[2,3][4] 0 2,3 4
fin- dp[1,2,...n-1][0]

2,3 - 0001100 - 12
dp[1][0]=0
dp[mask][i]=

*/
#include <fstream>
#include <vector>
using namespace std;
const int NMAX = 20;
int c[NMAX][NMAX];
vector<int> in[NMAX];
int dp[(1<<20)][NMAX];
int main()
{
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int n,m,x,y,z;
fin>>n>>m;
for(int i=0;i<=n;i++)
    for(int j=0;j<=n;j++)
        c[i][j]=1e9;
for(int i=0;i<m;i++)
{
    fin>>x>>y>>z;
    in[y].push_back(x);
    c[x][y]=z;
}
for(int mask=1;mask<(1<<n);mask++)
    for(int i=0;i<n;i++)
        dp[mask][i]=1e9;
dp[1][0]=0;

for(int mask=1;mask<(1<<n);mask++)
    for(int i=1;i<n;i++)
        if(mask&(1<<i))
            for(int k=0;k<in[i].size();k++)
                {
                int x = in[i][k];
                dp[mask][i] = min(dp[mask][i], c[x][i]+dp[mask-(1<<i)][x]);
                }
int res=1e9;
for(int i=1;i<n;i++)
    res=min(res,dp[(1<<n)-1][i]+c[i][0]);
if(res==1e9) fout<<"Nu exista solutie";
else fout<<res;
fin.close();fout.close();
return 0;
}