#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

const int MAXN=20;
const int MAXX=262150;
const int INF=100000000;
int n,m,i,j,k,cost[MAXN][MAXN],c[MAXX][MAXN];
vector <int> drum[MAXN];
int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        {
            cost[i][j]=INF;
        }
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            drum[y].push_back(x);
            scanf("%d",&cost[x][y]);
        }
     for(i=0;i<(1<<n);i++)
        for(j=0;j<n;j++)
        {
            c[i][j]=INF;
        }
    c[1][0]=0;
    for(i=0;i<(1<<n);i++)
        for(j=0;j<n;j++)
            if(i&(1<<j))
                for(k=0;k<drum[j].size();k++)
                    if(i&(1<<drum[j][k]))
                        c[i][j]=min(c[i][j],c[i^(1<<j)][drum[j][k]]+cost[drum[j][k]][j]);

    int rez=INF;
    for(k=0;k<drum[0].size();k++)
    {
        rez=min(rez,c[(1<<n)-1][drum[0][k]]+cost[drum[0][k]][0]);
    }

    if(rez==INF)
        printf("Nu exista solutie\n");
    else
        printf("%d",rez);
    return 0;
}