## Description

## Submission

class Solution {
public:
int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
vector<vector<int>> distance(n, vector<int>(n, 1e4 + 5));
for (auto& edge: edges) {
distance[edge[0]][edge[1]] = edge[2];
distance[edge[1]][edge[0]] = edge[2];
}
for (int k = 0; k < n; ++k) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
distance[i][j] = min(distance[i][j], distance[i][k] + distance[j][k]);
}
}
}
int smallestCnt = INT_MAX;
int ret;
for (int i = 0; i < n; ++i) {
int cnt = 0;
for (int j = 0; j < n; ++j) {
if (i == j) continue;
if (distance[i][j] <= distanceThreshold) cnt++;
}
if (cnt <= smallestCnt) {
smallestCnt = cnt;
ret = i;
}
}
return ret;
}
};