#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000007;
const int N = 81;
int n, m, p;
int c[N][N], f[N][N][N][2];
int main() {
  cin >> n >> p >> m;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) c[i][j] = INF;
  }
  for (int i = 1, x, y, dis; i <= m; ++i) {
    scanf("%d%d", &x, &y);
    scanf("%d", &dis);
    c[x][y] = min(dis, c[x][y]);
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      for (int k = 0; k <= p; ++k) {
        f[i][j][k][0] = f[i][j][k][1] = INF;
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    f[i][i][1][0] = f[i][i][1][1] = 0;
  }
  for (int d = 1; d < n; ++d) {
    for (int i = 1; i + d <= n; ++i) {
      int j = i + d;
      for (int k = 2; k <= p; ++k) {
        for (int i2 = i + 1; i2 < j; ++i2) {
          f[i][j][k][0] = min(f[i][j][k][0], f[i2][j][k - 1][0] + c[i][i2]);
          f[i][j][k][0] = min(f[i][j][k][0], f[i2][j][k - 1][1] + c[i][j]);
          f[i][j][k][0] = min(f[i][j][k][0], f[i2][j][k][0] + c[i][i2]);
          f[i][j][k][0] = min(f[i][j][k][0], f[i2][j][k][1] + c[i][j]);
        }
        f[i][j][k][0] = min(f[i][j][k][0], f[j][j][k - 1][0] + c[i][j]);
        f[i][j][k][0] = min(f[i][j][k][0], f[j][j][k][0] + c[i][j]);
        for (int j2 = j - 1; j2 > i; --j2) {
          f[i][j][k][1] = min(f[i][j][k][1], f[i][j2][k - 1][1] + c[j][j2]);
          f[i][j][k][1] = min(f[i][j][k][1], f[i][j2][k - 1][0] + c[j][i]);
          f[i][j][k][1] = min(f[i][j][k][1], f[i][j2][k][1] + c[j][j2]);
          f[i][j][k][1] = min(f[i][j][k][1], f[i][j2][k][0] + c[j][i]);
        }
        f[i][j][k][1] = min(f[i][j][k][1], f[i][i][k - 1][1] + c[j][i]);
        f[i][j][k][1] = min(f[i][j][k][1], f[i][i][k][1] + c[j][i]);
      }
    }
  }
  int ans = INF;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      ans = min(ans, f[i][j][p][0]);
      ans = min(ans, f[i][j][p][1]);
    }
  }
  cout << (ans == INF ? -1 : ans) << endl;
}
