#include <bits/stdc++.h>
using namespace std;
mt19937 Rand(time(0));
const int N = 80, M = 10, INF = (1 << 30) - 1;
int n, m, e[N + 9][N + 9];
void into() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) scanf("%d", &e[i][j]);
}
int col[N + 9], dp[M + 9][N + 9];
int Get_dp() {
  for (int i = 1; i <= n; ++i) col[i] = Rand() & 1, dp[0][i] = INF;
  dp[0][1] = 0;
  for (int i = 1; i <= m; ++i) {
    for (int j = 1; j <= n; ++j) dp[i][j] = INF;
    for (int j = 1; j <= n; ++j)
      for (int k = 1; k <= n; ++k)
        if (col[j] ^ col[k]) dp[i][k] = min(dp[i][k], dp[i - 1][j] + e[j][k]);
  }
  return dp[m][1];
}
int ans;
void Get_ans() {
  ans = INF;
  for (int i = 1; i <= 5000; ++i) ans = min(ans, Get_dp());
}
void work() { Get_ans(); }
void outo() { printf("%d\n", ans); }
int main() {
  int T = 1;
  for (; T--;) {
    into();
    work();
    outo();
  }
  return 0;
}
