class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        vector<vector<int>> grid(n, vector<int>(n, 10005));  // Since the maximum edge distance is 10^4

        // The distance from a node to itself is 0
        for (int i = 0; i < n; i++) grid[i][i] = 0;
        // Construct the adjacency matrix
        for (const vector<int>& e : edges) {
            int from = e[0];
            int to = e[1];
            int val = e[2];
            grid[from][to] = val;
            grid[to][from] = val; // Note that this is an undirected graph
        }

        // Begin Floyd-Warshall algorithm
        // Think about why p is placed in the outermost layer
        for (int p = 0; p < n; p++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    grid[i][j] = min(grid[i][j], grid[i][p] + grid[p][j]);
                }
            }
        }

        int result = 0;
        int count = n + 10; // Record the smallest number of cities connected within the range for all cities
        for (int i = 0; i < n; i++) {
            int curCount = 0; // Count how many cities a city can connect within the range
            for (int j = 0; j < n; j++) {
                if (i != j && grid[i][j] <= distanceThreshold) curCount++;
                // cout << "i:" << i << ", j:" << j << ", val: " << grid[i][j] << endl;
            }
            if (curCount <= count) { // Note that we use <= here
                count = curCount;
                result = i;
            }
        }
        return result;
    }
};