1#include <iostream>
2#include <vector>
3#include <climits>
4
5int findTheCity(int n, std::vector<std::vector<int>>& edges, int distanceThreshold) {
6    std::vector<std::vector<int>> dist(n, std::vector<int>(n, INT_MAX));
7    
8    for (int i = 0; i < n; ++i) dist[i][i] = 0;
9    
10    for (auto& edge : edges) {
11        int u = edge[0], v = edge[1], weight = edge[2];
12        dist[u][v] = weight;
13        dist[v][u] = weight;
14    }

    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (dist[i][k] < INT_MAX && dist[k][j] < INT_MAX && dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    int city = -1, minReachableCities = INT_MAX;
    for (int i = 0; i < n; ++i) {
        int reachableCities = 0;
        for (int j = 0; j < n; ++j) {
            if (i != j && dist[i][j] <= distanceThreshold) {
                ++reachableCities;
            }
        }
        if (reachableCities <= minReachableCities) {
            minReachableCities = reachableCities;
            city = i;
        }
    }
    return city;
}

int main() {
    int n = 4;
    std::vector<std::vector<int>> edges = {{0, 1, 3}, {1, 2, 1}, {1, 3, 4}, {2, 3, 1}};
    int distanceThreshold = 4;
    std::cout << findTheCity(n, edges, distanceThreshold) << std::endl;
    return 0;
}