#include <iostream>
using namespace std ;
int c[128][128] ;
int cost[128] ;
const int INF = 500000000 ;
int main() {
   int n, len ;
   cin >> n >> len ;
   for (int i=0; i<128; i++)
      for (int j=0; j<128; j++)
         c[i][j] = INF ;
   for (int i=0; i<n; i++) {
      char c1, c2 ;
      int cost ;
      cin >> c1 >> c2 >> cost ;
      c[(int)c1][(int)c2] = cost ;
   }
   for (int i=0; i<128; i++)
      if (len % 2 == 0)
         cost[i] = c[i][i] ;
      else
         cost[i] = 0 ;
   for (int it=2; it<len; it += 2) {
      int c2[128] ;
      for (int i=0; i<128; i++) {
         int nc = INF ;
         for (int j=0; j<128; j++)
            nc = min(nc, cost[j]+c[i][j]+c[j][i]) ;
         c2[i] = nc ;
      }
      for (int j=0; j<128; j++)
         cost[j] = c2[j] ;
   }
   int r = INF ;
   for (int i=0; i<128; i++)
      r = min(cost[i], r) ;
   if (r == INF)
      r = -1 ;
   cout << r << endl ;
}