#include <bits/stdc++.h>
using namespace std;
const int N = 85, MAX = 1e6 + 5;
int g[N][N], dp[N][N][N];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int n, k, m;
  cin >> n >> k >> m;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      for (int ki = 2; ki <= k; ki++) {
        dp[i][j][ki] = MAX;
      }
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      g[i][j] = MAX;
    }
  }
  for (int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    a--, b--;
    g[a][b] = min(g[a][b], c);
  }
  for (int z1 = 1; z1 < n; z1++) {
    for (int z2 = 0; z2 < n; z2++) {
      for (int ki = 2; ki <= k; ki++) {
        int i = z2;
        int j = z2 + z1;
        if (j >= n) {
          break;
        }
        dp[i][j][ki] = dp[i][j - 1][ki];
        for (int mid = i; mid < j; mid++) {
          dp[i][j][ki] = min(dp[i][j][ki], g[i][mid] + dp[mid][j][ki - 1]);
        }
        dp[i][j][ki] = min(dp[i][j][ki], g[i][j] + dp[j][i + 1][ki - 1]);
        dp[j][i][ki] = dp[j][i + 1][ki];
        for (int mid = i + 1; mid <= j; mid++) {
          dp[j][i][ki] = min(dp[j][i][ki], g[j][mid] + dp[mid][i][ki - 1]);
        }
        dp[j][i][ki] = min(dp[j][i][ki], g[j][i] + dp[i][j - 1][ki - 1]);
      }
    }
  }
  int ans = MAX;
  for (int i = 0; i < n; i++) {
    ans = min({ans, dp[i][n - 1][k], dp[i][0][k]});
  }
  if (ans >= MAX) {
    cout << "-1\n";
  } else {
    cout << ans << '\n';
  }
  return 0;
}
