import java.util.* ;
import java.io.*;
import java.util.ArrayList;
public class Solution {
public static int findTheCity(int n, ArrayList<ArrayList<Integer>> edges, int distanceThreshold) {
/*
Since here no source is given we need to find the cities with distance less than
threshold and return the max among those cities.
1. We can apply floyd marshal algorithm to find the shortest path from each and
every node to each and every node
Steps to apply floyd marshal
1. We will have a dist matrix of size n*n for 0 based indexing
2. All the diagonal elements will be 0.
3. We will covert undirected graph to directed by making edges both sides
4. We will update the given distance matrix with the given weights among nodes.
5. After that we will go via each node and calculate the distance matrix.
like a[i][j] = a[i][k] + a[k][j] if anyone of them is ifinity we can skip that
iteration
6. After our itration is done.
7. We will have two variables one minCities count for each city and cityValue.
8. We will try fo find the number of minCities within threshold for each node
and update the minCity variable
9. We will also update the city number
10. Since we are going from 0 to n we will have the largest city number
if num of mincities is same
*/
// creating the dist matrix
int[][] dist = new int[n][n];
// updating with infinity
for(int[] row: dist){
Arrays.fill(row, (int)1e9);
}
// updting the diagonal to 0 as going from 1 to 1 will be 0
for(int i=0; i<n; i++){
dist[i][i] = 0;
}
int m = edges.size();
// updating the given weights between nodes
for(int i=0; i<m; i++){
int u = edges.get(i).get(0);
int v = edges.get(i).get(1);
int distance = edges.get(i).get(2);
dist[u][v] = distance;
dist[v][u] = distance;
}
// aplying floyd marshal
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]==1e9 || dist[k][j]==1e9){
continue;
}
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
int minimumCityCount = Integer.MAX_VALUE;
int cityNo = 0;
//get mini city connected within threshold for each nodes
for(int i=0; i<n; i++){
int numOfCityConnected=0;
for(int j=0; j<n; j++){
if(dist[i][j]<=distanceThreshold){
numOfCityConnected++;
}
}
if(numOfCityConnected<=minimumCityCount){
minimumCityCount = numOfCityConnected;
cityNo = i;
}
}
return cityNo;
}
}