#include <bits/stdc++.h>
using namespace std;
int d[82][82][82][82];
vector<pair<int, int> > g[82];
int main() {
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  for (int i = 0; i < (int)(n + 1); ++i) {
    for (int j = 0; j < (int)(n + 1); ++j) {
      for (int k = 0; k < (int)(n + 1); ++k) {
        for (int l = 0; l < (int)(n + 1); ++l) {
          d[i][j][k][l] = 2000000000;
        }
      }
    }
  }
  int K, m;
  cin >> K >> m;
  for (int i = 0; i < (int)(m); ++i) {
    int x, y, z;
    cin >> x >> y >> z;
    --x;
    --y;
    g[x].push_back(make_pair(y, z));
  }
  for (int i = 0; i < (int)(n); ++i) {
    d[0][n][i][1] = 0;
  }
  for (int k = 1; k < K; ++k) {
    for (int l = 0; l < (int)(n); ++l) {
      for (int r = 1; r <= n; ++r) {
        for (int m = l; m < r; ++m) {
          for (int i = 0; i < (int)(g[m].size()); ++i) {
            int v = g[m][i].first, len = g[m][i].second;
            if (v < l || v >= r || v == m) {
              continue;
            }
            if (v < m) {
              d[l][m][v][k + 1] = min(d[l][m][v][k + 1], d[l][r][m][k] + len);
            } else {
              d[m + 1][r][v][k + 1] =
                  min(d[m + 1][r][v][k + 1], d[l][r][m][k] + len);
            }
          }
        }
      }
    }
  }
  int ans = 2000000000;
  for (int i = 0; i < (int)(n + 1); ++i) {
    for (int j = 0; j < (int)(n + 1); ++j) {
      for (int l = 0; l < (int)(n + 1); ++l) {
        ans = min(ans, d[i][j][l][K]);
      }
    }
  }
  if (ans == 2000000000) {
    cout << -1 << endl;
    return 0;
  }
  cout << ans << endl;
  return 0;
}
