#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <stack>
#define MAXK 17
#define MAXN 2003
using namespace std;

struct XYC{
  int x,y,c;
};

struct XC{
  int node,cost;
};

vector <XC> graf[MAXK];
vector <XC> arbo[MAXK];
queue <int> q;
int dina[MAXK][1<<MAXK];
int dist[MAXN];
int n,mi,k;

void AddEdge(XYC a){
  graf[a.x].push_back({a.y,a.c});
}

void DFS(int mask){
  int node,ans;
  for(node=0;node<n;node++){
    if(dina[node][mask]!=0){
      for(XC neigh : graf[node]){
        if((mask&(1<<neigh.node))==0){
          if(dina[node][mask]+neigh.cost<dina[neigh.node][mask+(1<<neigh.node)] || dina[neigh.node][mask+(1<<neigh.node)]==0){
            dina[neigh.node][mask+(1<<neigh.node)]=dina[node][mask]+neigh.cost;
          }
        }
      }
    }
  }
}

void BFS(int node){
  int i;
  for(i=1;i<n+1;i++){
    dist[i]=-1;
  }
  dist[node]=0;
  q.push(node);
  while(!q.empty()){
    node=q.front();
    q.pop();
    for(XC neigh : graf[node]){
      if(dist[neigh]==-1 || dist[neigh.node]>dist[node]+neigh.cost){
        dist[neigh.node]=dist[node]+neigh.cost;
      }
    }
  }
  for(i=0;i<k;i++){

  }
}

int main(){
  int m,i;
  XYC a;
  FILE *fin,*fout;
  fin=fopen("hamilton.in","r");
  fout=fopen("hamilton.out","w");
  fscanf(fin,"%d%d%d",&n,&m,&k);

  for(i=0;i<k;i++){

  }

  for(i=0;i<m;i++){
    fscanf(fin,"%d%d%d",&a.x,&a.y,&a.c);
    AddEdge(a);
  }

  dina[0][1]=1;

  for(i=1;i<(1<<n);i++){
    DFS(i);
  }

  mi=dina[k+1][(1<<(k+2))-1]-1;
  if(mi==-1){
    fprintf(fout,"Nu exista solutie");
  }else{
    fprintf(fout,"%d",mi-1);
  }

  fclose(fin);
  fclose(fout);
  return 0;
}