#include <bits/stdc++.h>
#include "towns.h"
template <class T>
using Vec = std::vector<T>;
int memo[110][110];
int getDist(const int i, const int j) {
if (i == j) return 0;
if (memo[i][j] == 0) {
memo[i][j] = memo[j][i] = getDistance(i, j);
}
return memo[i][j];
}
template <class Comp>
bool majority(const Vec<int> &vec, const Comp &comp) {
Vec<int> list, bucket;
for (const auto x: vec) {
if (list.empty() || !comp(list.back(), x)) {
list.push_back(x);
if (!bucket.empty()) {
list.push_back(bucket.back());
bucket.pop_back();
}
}
else {
bucket.push_back(x);
}
}
const auto T = list.back();
while (!list.empty()) {
if (comp(list.back(), T)) {
if (list.size() == 1) {
bucket.push_back(list.back());
list.pop_back();
}
else {
list.pop_back();
list.pop_back();
}
}
else {
if (bucket.empty()) {
return false;
}
list.pop_back();
bucket.pop_back();
}
}
return !bucket.empty();
}
int hubDistance(int N, int sub) {
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
memo[i][j] = 0;
}
}
const auto farthest = [&](const int src) {
Vec<int> v(N);
std::iota(v.begin(), v.end(), 0);
return *std::max_element(v.begin(), v.end(), [&](const int i, const int j) {
return getDist(src, i) < getDist(src, j);
});
};
const auto X = farthest(0);
const auto Y = farthest(X);
int R = 1000005;
std::map<int, Vec<int>> map;
Vec<int> near(N);
const auto Diameter = getDist(X, Y);
for (int u = 0; u < N; ++u) {
const auto x = getDist(X, u);
const auto z = ((x + getDist(0, u)) - getDist(X, 0)) / 2;
const auto l = x - z;
map[l].push_back(u);
R = std::min(R, std::max(l, Diameter - l));
near[u] = z;
}
Vec<Vec<int>> cand;
{
int left = 0;
for (const auto &[l, v]: map) {
if (std::max(left, N - (int) v.size() - left) * 2 <= N && std::max(l, Diameter - l) == R) {
cand.push_back(v);
}
left += (int) v.size();
}
}
if (cand.empty()) {
return -R;
}
for (const auto &v: cand) {
if ((int) v.size() * 2 <= N) {
return R;
}
}
Vec<char> is_cand(N);
for (const auto x: cand[0]) {
is_cand[x] = true;
}
const auto same = [&](const int x, const int y) {
if (!is_cand[x] || !is_cand[y]) return false;
return getDist(x, y) < near[x] + near[y];
};
Vec<int> tmp(N);
std::iota(tmp.begin(), tmp.end(), 0);
return majority(tmp, same) ? -R : R;
}
#ifdef LOCAL
int dist[110][110];
int getDistance(int i, int j) {
return dist[i][j];
}
int main() {
int sub, tests;
std::cin >> sub >> tests;
while (tests--) {
int N;
std::cin >> N;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
std::cin >> dist[i][j];
}
}
std::cout << hubDistance(N, sub) << '\n';
}
return 0;
}
#endif
