There are n cities numbered from 0 to n-1. Given the array edges where edges[i] = [fromi, toi, weighti] represents a bidirectional and weighted edge between cities fromi and toi, and given the integer distanceThreshold.
Return the city with the smallest number of cities that are reachable through some path and whose distance is at most distanceThreshold, If there are multiple such cities, return the city with the greatest number.
Notice that the distance of a path connecting cities i and j is equal to the sum of the edges' weights along that path.
 
Example 1:

Input: n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
Output: 3
Explanation: The figure above describes the graph. 
The neighboring cities at a distanceThreshold = 4 for each city are:
City 0 -> [City 1, City 2] 
City 1 -> [City 0, City 2, City 3] 
City 2 -> [City 0, City 1, City 3] 
City 3 -> [City 1, City 2] 
Cities 0 and 3 have 2 neighboring cities at a distanceThreshold = 4, but we have to return city 3 since it has the greatest number.

Example 2:

Input: n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2
Output: 0
Explanation: The figure above describes the graph. 
The neighboring cities at a distanceThreshold = 2 for each city are:
City 0 -> [City 1] 
City 1 -> [City 0, City 4] 
City 2 -> [City 3, City 4] 
City 3 -> [City 2, City 4]
City 4 -> [City 1, City 2, City 3] 
The city 0 has 1 neighboring city at a distanceThreshold = 2.

 
Constraints:

2 <= n <= 100
1 <= edges.length <= n * (n - 1) / 2
edges[i].length == 3
0 <= fromi < toi < n
1 <= weighti, distanceThreshold <= 10^4
All pairs (fromi, toi) are distinct.

Difficulty: interview

Starter code:

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        

Solutions:
class Solution:
    def findTheCity(self, n, edges, threshold):
        adj=[[] for _ in range(n)]
        for u,v,w in edges:
            adj[u].append((w,v))
            adj[v].append((w,u))

        ans=mn=100
        for x in range(n):
            cur=1
            vis={x}
            dist=[threshold+1]*n
            hp=[(0,x)]
            while hp:
                d,u=heappop(hp)
                if d>dist[u]:
                    continue
                for w,v in adj[u]:
                    if d+w<dist[v]:
                        vis.add(v)
                        dist[v]=d+w
                        heappush(hp,(d+w,v))
            if len(vis)<=mn:
                mn=len(vis)
                ans=x
        
        return ans

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], limit: int) -> int:
        graph = collections.defaultdict(lambda: [])
        for n1, n2, w in edges:
            graph[n1].append((n2, w))
            graph[n2].append((n1, w))
        def dijkstra(s):
            ret = 0
            dist = [float('inf')]*n
            dist[s] = 0
            heap = [(0, s)]
            seen = set()
            while heap:
                cur_w, cur = heapq.heappop(heap)
                if cur in seen:
                    continue
                seen.add(cur)
                
                ret += 1
                for node, w in graph[cur]:
                    if dist[node] > cur_w+w:
                        dist[node] = cur_w+w
                        if dist[node] <= limit:
                            heapq.heappush(heap, (dist[node], node))
            return ret-1
        
        return sorted([i for i in range(n)], key = lambda x:[dijkstra(x), -x])[0]
                            


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:             
        graph = {i: [] for i in range(n)}
        # a. create our bidirectional graph with the weights
        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, w))
        # b. loop over the nodes and retain the minimum cities visited
        res = 0, math.inf
        for i in range(n):
            visited = set()
            q = []
            heappush(q, (0, i))
            cities = 0
            # pop from
            while q:
                current_weight, node = heappop(q)
                if node in visited:
                    continue
                visited.add(node)
                cities += 1
            # loop over neighbors and append only if not visited and weight <= threshold
                for neighbor, neighbor_weight in graph[node]:
                    if neighbor not in visited and current_weight + neighbor_weight <= distanceThreshold:
                        heappush(q, (current_weight + neighbor_weight, neighbor))

            # when the queue is empty, if cities <= res[1]: res = (i, weight)
            if cities - 1 <= res[1]:
                res = i, cities - 1

        return res[0]

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
                
        # Floyd-warshall
        
        dp = [[float('inf') for _ in range(n)] for _ in range(n)]
        for ed in edges:
            u, v, weight = ed[0], ed[1], ed[2]
            dp[u][v] = dp[v][u] = weight
        
        for k in range(n):
            for u in range(n):
                for v in range(n):
                    dp[u][v] = min(dp[u][v], dp[u][k] + dp[k][v])
        
        ans = -1
        min_neighbor = float('inf')
        for u in range(n):
            cur_neighbor = 0
            for v in range(n):
                if v != u and dp[u][v] <= distanceThreshold:
                    cur_neighbor += 1
            if cur_neighbor <= min_neighbor:
                min_neighbor = cur_neighbor
                ans = u
        
        return ans

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        dist = [[float('inf')] * n for _ in range(n)]
        for u, v, w in edges:
            dist[u][v] = w
            dist[v][u] = w
        for u in range(n):
            dist[u][u] = 0
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if dist[i][j] > (d := dist[i][k] + dist[k][j]):
                        dist[i][j] =  d
        neighbors = {len(list([x for x in dist[i] if 0 < x <= distanceThreshold])): i for i in range(n)}
        return neighbors[min(neighbors)]


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
        graph=[]
        
        for i in range(n):
            graph.append([float('inf')]*n)                
        
        for i in range(n):
            graph[i][i] = 0
        
        for [edge1,edge2, weight] in edges:
            graph[edge1][edge2] = weight
            graph[edge2][edge1] = weight
            
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    graph[i][j] = min(graph[i][j],graph[i][k] + graph[k][j])
             
        minNode = -1
        minCount = 101
        
        for i in range(n):
            count = 0
            for j in range(n):
                if(graph[i][j]<=distanceThreshold):
                    count+=1
            
            
            if count <= minCount:
                minCount = count
                minNode = i
            
        return minNode


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        distances=[[sys.maxsize] *n for _ in range(n)]
        
        for u,v,w in edges:
            distances[u][v]=w
            distances[v][u]=w
            
        for i in range(n):
            distances[i][i]=0
            
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    distances[i][j]=min(distances[i][j], distances[i][k]+distances[k][j])
                    
        counts={}
        
        for i, dist in enumerate(distances):
            counts[len([d for d in dist if d<=distanceThreshold])]=i
        
        return counts[min(counts)]


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
        dp = [[float('inf') for _ in range(n)] for _ in range(n)]
        
        for s, e, w in edges:
            dp[s][e] = w
            dp[e][s] = w
        
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
                    
                    
        minlen = n
        res = -1

        for i, row in enumerate(dp):
            cnt = sum(v <= distanceThreshold and j != i for j, v in enumerate(row))
            if cnt <= minlen:
                minlen = cnt
                res = i
                
        return res

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        paths = []
        for i in range(n): paths.append([sys.maxsize] * n)
        
        # all non edges are inf
        # all self paths are 0
        for src,dest,weight in edges:
            paths[src][dest] = weight
            paths[dest][src] = weight
        for i in range(n): paths[i][i] = 0
      
        # calculate all source shortest paths
        for k in range(n):
            for src in range(n):
                for dest in range(n):
                    paths[src][dest] = min(paths[src][dest], paths[src][k] + paths[k][dest])

        globalNode = -1
        globalReachable = sys.maxsize

        for i in range(n):
            localNode = i
            localReachable = 0
            
            for j in range(n):
                if paths[i][j] <= distanceThreshold and j != i: 
                    localReachable += 1
                
            if localReachable < globalReachable: 
                globalReachable = localReachable
                globalNode = localNode

            elif localReachable == globalReachable and localNode > globalNode:
                globalNode = localNode
                
        return globalNode


from typing import List
from collections import defaultdict

class Solution:
\tdef findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
\t\tdist = [[float('inf')] * n for _ in range(n)]
\t\tfor u, v, w in edges:
\t\t\tdist[u][v] = dist[v][u] = w # bidirectional edges
\t\tfor i in range(n):
\t\t\tdist[i][i] = 0

\t\t# floyd-warshall
\t\tfor k in range(n):
\t\t\tfor i in range(n):
\t\t\t\tfor j in range(n):
\t\t\t\t\tdist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
\t\t
\t\tprint(dist)

\t\tres = {sum(v <= distanceThreshold for v in dist[u]): u for u in range(n)}
\t\t
\t\treturn res[min(res)]

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        d = [[float('inf') for _ in range(n)] for _ in range(n)]

        # Floyd Warshall
        # bases cases
        for s, t, w in edges:
            d[s][t] = w
            # add in opposite
            d[t][s] = w

        # get all paths from node
        for i in range(n):
            for s in range(n):
                for t in range(n):
                    d[s][t] = min(d[s][t], d[s][i] + d[i][t])

        neighbors = [0 for i in range(n)]
        for s in range(n):
            for t in range(n):
                if s != t and d[s][t] <= distanceThreshold:
                    neighbors[s] += 1

        min_value = float('inf')
        res = None

        for v in range(n):
            if neighbors[v] <= min_value:
                min_value = neighbors[v]
                res = v

        return res


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        dis=[[float(inf)] * n for _ in range(n)]
        for i,j,w in edges:
            dis[i][j]=w
            dis[j][i]=w
        for i in range(n):
            dis[i][i] = 0
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j])
        
        res = {sum(d<=distanceThreshold for d in dis[i]) : i for i in range(n)}
        print(res)
        return res[min(res)]
        
        ''' dfs not working, https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/discuss/490555/The-Reason-of-DFS-Not-Working-(Explain-Graph-and-Example)
        d = collections.defaultdict(list)
        lookup = dict({})
        for e in edges:
            s, e, l = e[0], e[1], e[2]
            d[s].append(e)
            d[e].append(s)
            lookup[(s,e)]=l
            lookup[(e,s)]=l
        
        res=collections.defaultdict(list)
        def dfs(j: int, i:int, t:int, v:set):

            for c in d[i]:
                if c not in v and c != j and lookup[(i,c)] <= t:
                    res[j].append(c)
                    v.add(c)
                    dfs(j, c, t-lookup[i,c], v)
                
        
        for i in range(n):
            dfs(i, i, distanceThreshold, set({}))
        if n > 26:
            print(\"27={},33={}\".format(res[27], res[33]))
        mm = len(res[0])
        r = 0
        for i in range(n):
            print(\"{},len:{}\".format(i, len(res[i])))
            if len(res[i])  <= mm:
                r = i
                mm = len(res[i])
        return r
        '''

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
        graph = collections.defaultdict(list)
        
        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, w))
            
        dist = collections.defaultdict(list)
        self.min = float('inf')
        def getNumberOfNeighbors(city):
            heap = [(0, city)]
            count = 0
            seen = set()
            while heap:
                currW, u = heapq.heappop(heap)
                if u in seen:
                    continue
                seen.add(u)
                for v, w in graph[u]:
                    if v in seen:
                        continue
                    if currW + w <= distanceThreshold:
                        heapq.heappush(heap, (currW + w, v))
                count += 1
            return count
        
        for city in range(n):
            num = getNumberOfNeighbors(city)
            dist[num].append(city)
            self.min = min(self.min, num)
        
        return max(dist[self.min])

class Solution:
    def findTheCity2(self, n: int, edges: List[List[int]], dt: int) -> int:
        \"\"\"Floyd-warshall, O(n^3)\"\"\"
        dist = [[float('inf')] * n for _ in range(n)]
        for i in range(n):
            dist[i][i] = 0
        for u, v, w in edges:
            dist[u][v] = w
            dist[v][u] = w
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        res, con = -1, float('inf')
        for i in range(n):
            cur = sum(dist[i][j] <= dt for j in range(n))
            if cur <= con:
                con = cur
                res = i
        return res
    
    def findTheCity(self, n: int, edges: List[List[int]], dt: int) -> int:
        g = collections.defaultdict(list)
        for u, v, w in edges:
            g[u].append((v, w))
            g[v].append((u, w))
        def dijkstra(src):
            pq = [(0, src)]
            seen = set()
            res = 0
            while pq:
                d, cur = heapq.heappop(pq)
                if d > dt or cur in seen:
                    continue
                seen.add(cur)
                res += 1
                for nei, nw in g[cur]:
                    if nei not in seen:
                        heapq.heappush(pq, (d + nw, nei))
            return res
        dp = [dijkstra(i) for i in range(n)]
        mn = float('inf')
        res = -1
        for i, num in enumerate(dp):
            if num <= mn:
                mn = num
                res = i
        return res
        
                
        
                        

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
#         FLOYD WARSHALL 
            
        dist = [[float('inf') for j in range(n)] for i in range(n)]
        
        for edge in edges:
            dist[edge[0]][edge[1]] = edge[2]
            dist[edge[1]][edge[0]] = edge[2]
        
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])
        
        curr = 0
        res_idx = 0
        count = float('inf')
        
        for i in range(n):
            curr = 0
            for j in range(n):
                if i!=j and dist[i][j] <= distanceThreshold:
                    curr += 1
            
            if curr <= count:
                count = curr
                res_idx = i
        
        return res_idx
        
        
        


class Solution:
    def findTheCity(self, n, edges, maxd):
        \"\"\"
        * dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
        # res = {sum(d <= maxd for d in dis[i]): i for i in range(n)}
        \"\"\"
        
        \"\"\"
        城市i到城市j的距離矩陣:
        [[0, 2, 5, 5, 4], 
         [2, 0, 3, 3, 2], 
         [5, 3, 0, 1, 2], 
         [5, 3, 1, 0, 1], 
         [4, 2, 2, 1, 0]]
        \"\"\"
        dis = [[float('inf')] * n for _ in range(n)] # 城市i到城市j的距離矩陣
        for i, j, w in edges:
            dis[i][j] = dis[j][i] = w
        
        for i in range(n):
            dis[i][i] = 0
        
        # ### wrong!
        # for i in range(n):
        #     for j in range(n):
        #         for k in range(n):
        
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
        
        res = {sum(d <= maxd for d in dis[i]): i for i in range(n)} # {數目: 城市}
        return res[min(res)]

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        INF=9999999
        dist=[[INF for j in range(n)] for i in range(n)]
        graph=[[]for i in range(n)]
        for e in edges:
            i=e[0]
            j=e[1]
            dist[i][j]=e[2]
            dist[j][i]=e[2]
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if i!=j:
                        dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
        #print(dist)
        ans=-1
        mm=n
        for i in range(n):
            k=0
            for j in range(n):
                if dist[i][j]<=distanceThreshold:
                    k+=1
            if k<=mm:
                mm=k
                ans=i
        return ans

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
 
        dist = [ [math.inf]*n  for _ in range(n) ]
        for i,j,w in edges:
            dist[i][j] = w
            dist[j][i] = w
        
        for i in range(n):
            dist[i][i] = 0
        
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
        
        res = []
        for i in range(n):
            res.append( sum( dist[i][j]<=distanceThreshold for j in range(n) ) )
        
        print(res)
        
        tmp = (n, 0)
        for i,c in enumerate(res):
            # print(tmp)
            if (c,-i) < tmp:
                tmp = (c,-i)
            
        return -tmp[1]
        
        
        
        
        
#         graph = collections.defaultdict(list)
#         for i,j,w in edges:
#             graph[i].append([j,w])
#             graph[j].append( [i, w] )
        
        
#         res = [0]*n
        
#         for i in range(n):
#             print('start')
#             print(i)
#             visited = set([i])
#             que = collections.deque([ (i,0) ])
#             while que:
#                 cur, dist = que.popleft()
#                 for j,w in graph[cur]:
#                     print([j, dist+w] )
#                     if j not in visited and dist+w<=distanceThreshold:
                        
#                         visited.add(j)
#                         que.append( [j,dist+w ] )
#                         res[i]+=1
        
#         # print(res)
        
#         m = min(res)
#         for i in range(n-1, -1, -1):
#             if res[i] == m:
#                 return i
            
                        
        
        


from collections import defaultdict

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        cityGraph = [[float(\"inf\") for col in range(n)] for row in range(n)]
        for edge in edges:
            cityGraph[edge[0]][edge[1]] = edge[2]
            cityGraph[edge[1]][edge[0]] = edge[2]
            
        
        for intermediateCity in range(n):
            for startCity in range(n):
                for endCity in range(n):
                    if startCity != endCity:
                        cityGraph[startCity][endCity] = min(cityGraph[startCity][endCity], cityGraph[startCity][intermediateCity]+cityGraph[intermediateCity][endCity])
        
        cityThresholdSum = [sum(1 for cityDist in city if cityDist <= distanceThreshold) for city in cityGraph]
        
        return len(cityThresholdSum) - 1 -cityThresholdSum[::-1].index(min(cityThresholdSum))

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        # 构建dist矩阵
        dist = [[float('inf')] * n for _ in  range(n)]
        for i, j, w in edges:
            dist[i][j] = w
            dist[j][i] = w
        for i in range(n):
            dist[i][i] = 0
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

        # 过滤
        res = 0
        minCnt = float('inf')
        for i in range(n):
            cnt = 0
            for d in dist[i]:
                if d <= distanceThreshold:
                    cnt += 1
            if cnt <= minCnt:
                minCnt = cnt
                res = i
        return res


def buildGraph(n, edges):
    graph = [[float('inf')]*n for _ in range(n)]
    for e in edges:
        graph[e[0]][e[1]] = e[2]
        graph[e[1]][e[0]] = e[2]

    '''
    Floyed-Warshall algorithm won't work if diagonal values are not set to 
    0 when self loop distance is not given
    '''
    for i in range(n):
        graph[i][i] = 0
    
    return graph
def floyedWarshalAllPairDist(graph):
    n = len(graph)
    for i in range(n):
        for j in range(n):
            for k in range(n):
                graph[j][k] = min(graph[j][k], graph[j][i]+graph[i][k])
    
'''
Algorithm: 
1) Measure all pair distance using Floyed Warshal algorithm
2) Find the city with minimum connected cities with atmost threshold distance
'''
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
        '''
        graph = buildGraph(n, edges)
        floyedWarshalAllPairDist(graph)
        
        min_city = 0
        min_count = float('inf')
        for i in range(n):
            count = sum([1 if x<=distanceThreshold else 0 for x in graph[i]])
            if count <= min_count:
                min_count = count
                min_city = i
        
        return min_city
        '''
        g = [[float('inf')]*n for _ in range(n)]
        for u,v,w in edges:
            g[u][v] = w
            g[v][u] = w
        
        for i in range(n):
            for u in range(n):
                for v in range(n):
                    if u==v: 
                        g[u][v]=0
                    else:
                        g[u][v] = min(g[u][v], g[u][i]+g[i][v])
        
        city, count = -1,float('inf')
        for i in range(n):
            tmp = sum(1 for x in g[i] if x<=distanceThreshold)
            if tmp<=count:
                city = i
                count = tmp
        
        return city
        
        
        
        
        


import sys
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        dist = arr = [[10001 if i!=j else 0 for i in range(n)] for j in range(n)]
        
        for source, target, weight in edges:
            dist[source][target] = weight
            dist[target][source] = weight
        
        # implementing floyd-warshall
        for node in range(n):
            for source in range(n):
                for target in range(n):
                    new_dist = dist[source][node] + dist[node][target]
                    #if source == target: new_dist = 0
                    dist[source][target] = min(dist[source][target], new_dist)
                    
        #print(dist)
        ncity = [n]*n
        for dindex, dlist in enumerate(dist):
            ncity[dindex] = [index for index, i in enumerate(dlist) if i <= distanceThreshold and i != 0]
            
        for source, cities in enumerate(ncity):
            for target in cities:
                if source not in ncity[target]: ncity[target].append(source)
                    
        #print(ncity)
        min_count = 10001
        index = 0
        for cindex, city in enumerate(ncity):
            len_city = len(city)
            if len_city <= min_count:
                min_count = len_city
                index = cindex
        return index

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        def dij(arr, i):
            passed = [i]
            notpass = [j for j in range(len(arr)) if j != i ]
            dis = arr[i]
            while notpass:
                index = notpass[0]
                for node in notpass:
                    if dis[node] < dis[index]:
                        index = node
                passed.append(index)
                notpass.remove(index)
                
                for x, total in enumerate(dis):
                    dis[x] = min(dis[x], dis[index] + arr[index][x])
            return dis
                    
            
        arr = [[float('inf') for x in range(n)] for y in range(n)]  
        for i in range(n):
            arr[i][i] = 0
            
        for fromi, toj, val in edges:
            arr[fromi][toj] = val
            arr[toj][fromi] = val
            
        min_nums, min_indexes = float('inf'), []
        for i in range(n):
            dis = dij(arr, i)
            nums = len([length for length in dis if length <= distanceThreshold])
            if nums < min_nums:
                min_nums = nums
                min_indexes = [i]
            elif nums == min_nums:
                min_indexes.append(i)
                
        return max(min_indexes)
            


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        \"\"\"priority queue + bfs \"\"\"
        graph = defaultdict(list)
        for st, ed, w in edges:
            graph[st].append((w, ed))
            graph[ed].append((w, st))

        opt = float(\"inf\")
        ans = 0
        for i in range(n):
            cnt = self.numofNeighbor(n, graph, distanceThreshold, i)            
            if cnt <= opt:
                ans, opt = i, cnt
        return ans

    def numofNeighbor(self, n, graph, distancTreshold, node):
        queue = []
        queue.append((0, node))
        visited = [False for _ in range(n)]
        cnt = 0
        while queue:
            w, v = heappop(queue)
            if visited[v]:
                continue
            cnt += 1
            visited[v] = True

            for d, neighbor in graph[v]:
                if visited[neighbor]:
                    continue
                if d + w > distancTreshold:
                    continue
                heappush(queue, (w+d, neighbor))

        return cnt

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        storage = [[30000 if i != j else 0 for i in range(n) ] for j in range(n)]
        for edge in edges:
            storage[edge[0]][edge[1]] = edge[2]
            storage[edge[1]][edge[0]] = edge[2]
        
        #FloydWarshallAPSP
        for k in range(0, n):
            for i in range(0, n):
                for j in range(0, n):
                    currD = storage[i][j]
                    toK = storage[i][k]
                    fromK = storage[k][j]
                    storage[i][j] = min(storage[i][j], toK + fromK)
        
        #Process to get answer
        currLowestCity = 0
        currLowestCount = 200
        for i in range(0, n):
            count = 0
            for j in range(0, n):
                if storage[j][i] <= distanceThreshold:
                    count += 1
            if count <= currLowestCount:
                currLowestCity = i
                currLowestCount = count
        
        return currLowestCity


class Solution:
    
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        dp = [[float('inf')]*n for _ in range(n)]
        for i, j, w in edges:
            dp[i][j] = dp[j][i] = w
        for i in range(n):
            dp[i][i] = 0
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
        min_idx, min_val = None, None
        for i in range(n):
            can_val = sum(v <= distanceThreshold for v in dp[i])
            if min_val is None or can_val <= min_val:
                min_val = can_val
                min_idx = i
        return min_idx 
        
        
        
        
        
            


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        storage = [[30000 if i != j else 0 for i in range(n) ] for j in range(n)]
        for edge in edges:
            storage[edge[0]][edge[1]] = edge[2]
            storage[edge[1]][edge[0]] = edge[2]
        
        #FloydWarshallAPSP
        for k in range(0, n):
            for i in range(0, n):
                for j in range(0, n):
                    currD = storage[i][j]
                    toK = storage[i][k]
                    fromK = storage[k][j]
                    storage[i][j] = min(storage[i][j], toK + fromK)
                    
        print(\"storage\", storage)
        
        #Process to get answer
        currLowestCity = 0
        currLowestCount = 200
        for i in range(0, n):
            count = 0
            for j in range(0, n):
                if storage[j][i] <= distanceThreshold:
                    count += 1
            if count <= currLowestCount:
                currLowestCity = i
                currLowestCount = count
        
        return currLowestCity


from collections import defaultdict
class Solution:
    
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        dis = [[float('inf')] * n for _ in range(n)]
        for i, j, w in edges:
            dis[i][j] = dis[j][i] = w
        for i in range(n):
            dis[i][i] = 0
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
        res = {sum(d <= distanceThreshold for d in dis[i]): i for i in range(n)}
        return res[min(res)]
        
            


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        graph=[[99999 for j in range(n)]for k in range(n)]
        dict1={}
        for u,v,w in edges:
            graph[u][v]=w
            graph[v][u]=w
        for i in range(n):
            graph[i][i]=1
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    graph[i][j]=min(graph[i][j],graph[i][k]+graph[k][j])
        ans=-1
        min1=999999999
        for i in range(n):
            count=0
            for j in range(n):
                if(graph[i][j] <= distanceThreshold):
                    count+=1
            #print(count)
            if(count <= min1):
                min1=count
                ans=i
        return ans


class Solution:
    
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        dp = [[float('inf')]*n for _ in range(n)]
        for i, j, w in edges:
            dp[i][j] = dp[j][i] = w
        for i in range(n):
            dp[i][i] = 0
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
        res = {sum(v <= distanceThreshold for v in dp[i]): i for i in range(n)}
        return res[min(res)]
        
        
        
        
        
            


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        AdjMat = [[float('inf')] * n for _ in range(n)]
        
        for i in range(n):
            AdjMat[i][i] = 0
            
        for u,v,w in edges:
            AdjMat[u][v] = w
            AdjMat[v][u] = w
            
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    AdjMat[i][j] = min(AdjMat[i][j],AdjMat[i][k] + AdjMat[k][j])
                    
        d = {}
        for i in range(n):
            c = -1
            for j in range(n):
                if AdjMat[i][j] <= distanceThreshold:
                    c += 1
                    
            d[i] = c
            
        m = min(d.values())
        res = 0
        for k in d:
            if d[k] == m:
                res = max(res,k)
        return res
                


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        adj = [[float('inf')] * n for i in range(n)]
        
        for i in range(n):
            adj[i][i] = 0
        
        for u,v,w in edges:
            adj[u][v] = w
            adj[v][u] = w
            
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j])
                    
        print(adj)
        
        res = float('inf')
        res_city = -1
        for i in range(n):
            count = 0
            for j in range(n):
                if i != j:
                    if adj[i][j] <= distanceThreshold:
                        count += 1                        
            if count <= res:
                res = count
                res_city = i
            
        return res_city


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        dis = [[float('inf')] * n for _ in range(n)]
        
        for i, j, w in edges:
            dis[i][j] = dis[j][i] = w
            
        for i in range(n):
            dis[i][i] = 0
            
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
        
        print(dis)
        ans = 0
        mmin = n
        for i in range(n):
            count = 0
            for j in range(n):
                if dis[i][j] <= distanceThreshold:
                    count += 1
            if count <= mmin:
                mmin = count
                ans = i
        return ans

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        # Floyd-Warshall: shortest path between all pairs of vertices, negative edges allowed
        # Dijkstra's: shortest path from one node to all nodes
        # Bellman-Ford: shortest path from one node to all nodes, negative edges allowed
        dis = [[float('inf') for _ in range(n)] for _ in range(n)]
        for i, j, w in edges:
            dis[i][j] = dis[j][i] = w
        for i in range(n):
            dis[i][i] = 0
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j])
        # res = {sum(d <= distanceThreshold for d in dis[i]): i for i in range(n)}
        res = {}
        for i in range(n):
            count = 0
            for d in dis[i]:
                if d <= distanceThreshold:
                    count += 1
            res[count] = i

        return res[min(res)]
        
        # Dijkstra
#         weight = collections.defaultdict(dict)
#         for u, v, w in edges:
#             weight[u][v] = w
#             weight[v][u] = w
        
#         def getNumberOfNeighbors(city):
#             heap = [(0, city)]
#             dist = {}
            
#             while heap:
#                 w, u = heapq.heappop(heap)
#                 if u not in dist and u != city:
#                     dist[u] = w
#                 for v in weight[u]:
#                     if v in dist:
#                         continue
#                     if w + weight[u][v] <= distanceThreshold:
#                         heapq.heappush(heap, (w+weight[u][v], v))
#             return len(dist)
#         minCount = float('inf')
#         ans = None
#         for i in range(n):
#             count = getNumberOfNeighbors(i)
#             if count <= minCount:
#                 ans = i
#                 minCount = count
#         return ans


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        graph = collections.defaultdict(list)
        res = float('inf')
        min_city = 0
        for u, v, w in edges:
            graph[u].append(( w, v))
            graph[v].append((w, u))
        def djikstra(node):
            distance = {nid: float('inf') for nid in list(graph.keys())}
            distance[node] = 0
            heap = [(0, node)]
            heapq.heapify(heap)
            total = 0
            while heap:
                d, nd = heapq.heappop(heap)
                if d > distance[nd]:
                    continue
                for nei in graph[nd]:
                    nei_cost, nei_id = nei
                    total = (d + nei_cost)
                    if total < distance[nei_id]:
                        distance[nei_id] = total
                        heapq.heappush(heap, (total, nei_id))
            return sum(dis <= distanceThreshold for dis in list(distance.values()))  - 1
        res = {djikstra(i):i for i in range(n)}
        return res[min(res)]
        
        
                       


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        # Floyd-Warshall: shortest path between all pairs of vertices, negative edges allowed
        # Dijkstra's: shortest path from one node to all nodes
        # Bellman-Ford: shortest path from one node to all nodes, negative edges allowed
        dis = [[float('inf') for _ in range(n)] for _ in range(n)]
        for i, j, w in edges:
            dis[i][j] = dis[j][i] = w
        for i in range(n):
            dis[i][i] = 0
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j])
        # res = {sum(d <= distanceThreshold for d in dis[i]): i for i in range(n)}
        res = {}
        for i in range(n):
            count = 0
            for d in dis[i]:
                if d <= distanceThreshold:
                    count += 1
            res[count] = i

        return res[min(res)]

class Solution:
    def findTheCity(self, N: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
        dist = [[float('inf')] * N for _ in range(N)]
        
        for u in range(N):
            dist[u][u] = 0
            
        for u, v, w in edges:
            dist[u][v] = w
            dist[v][u] = w
            
        # Floyd
        for k in range(N):
            for j in range(N):
                for i in range(N):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        
        # Calculate
        min_cities = float('inf')
        ret = None
        print(dist)
        
        for u in range(N):
            reach = 0
            for v in range(N):
                if u != v and dist[u][v] <= distanceThreshold:
                    reach += 1
            
            if reach <= min_cities:
                min_cities = reach
                ret = u
                
        return ret
            
        


class Solution:
    def findTheCity(self, n, edges, maxd):
        \"\"\"
        * dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
        # res = {sum(d <= maxd for d in dis[i]): i for i in range(n)}
        \"\"\"
        dis = [[float('inf')] * n for _ in range(n)]
        for i, j, w in edges:
            dis[i][j] = dis[j][i] = w
        for i in range(n):
            dis[i][i] = 0
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
        res = {sum(d <= maxd for d in dis[i]): i for i in range(n)}
        return res[min(res)]


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:

        matrix = [[float('inf') for x in range(n)] for y in range(n)]
        
        # populate self loops
        for i in range(n):
            matrix[i][i] = 0
        
        # populate initial matrix
        for u,v,w in edges:
            matrix[u][v] = w
            matrix[v][u] = w

        # floyd-warshall       
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    matrix[i][j] = min(matrix[i][j], matrix[i][k]+matrix[k][j])                  
        
        # get amount of below threshold cities
        res = Counter()
        for i, row in enumerate(matrix):
            for j, dist in enumerate(row):
                if dist <= distanceThreshold and i != j :
                    res[i] += 1
        
        best = 0
        for i in range(n):
            if res[i] <= res[best]:
                best = i
        return best
        
        # check if unconnected cities
        unconnected = []
        i = 0
        while i < n:
            if res[i] == 0:
                # not conencted
                unconnected.append(i)
            i += 1
                
        if len(unconnected) == 1:
            return unconnected[0]
        elif len(unconnected) > 1:
            return max(unconnected)
            
        # all cities are connected with each other, get min value
        ans = min(res.values())
        max_city = 0
        
        # if multiple cities with same minimum neighbours, select biggest one
        for city in range(len(res)):
            if res[city] <= ans and city > max_city:
                max_city = city
                

        return max_city

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        dis = [[9999999] * n for _ in range(n)]
        
        for i, j, w in edges:
            dis[i][j] = dis[j][i] = w
        for i in range(n):
            dis[i][i] = 0
        
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
        print(dis)
        
        m, ans = n, 0
        for i in range(n):
            c = 0
            for j in range(n):
                if(dis[i][j] <= distanceThreshold):
                    c += 1
            if(c <= m):
                ans = i
                m = c
        return ans    
                
                


import heapq
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        graph = []
        for _ in range(n):
            graph.append([float('inf')]*n)
        
        for i,j,w in edges:
            graph[i][j] = w
            graph[j][i] = w
        
        
        nums = []
        for i in range(n):
            ans = self.dijkstra(graph, i, distanceThreshold)
            nums.append(ans)
        
        ans = 0
        minW = float('inf')
        for i, w in enumerate(nums):
            if w <= minW:
                minW = w
                ans = i
        return ans
            
        
    def dijkstra(self, graph, idx, threshold):
        dist = [(w, i) for i,w in enumerate(graph[idx]) if w != float('inf')]
        heapq.heapify(dist)
        ans = []
        visited = {idx}
        while len(dist) > 0 and dist[0][0] <= threshold and len(visited) <= len(graph):
            cur_w, i = heapq.heappop(dist)
            if i not in visited:
                ans.append(i)
                visited.add(i)
                for j, w in enumerate(graph[i]):
                    if w != float('inf'):
                        heapq.heappush(dist, (w+cur_w,j))
        return len(ans)
            
            
            


class Solution:
    def dfs(self, q, D, V, k):
        Q = [q]
        V[q] = 0
        while Q:
            T = []
            for nd in Q:
                W = V[nd]
                for n,w in D[nd]:
                    cl = W + w
                    cr = V[n]                
                    if cl < cr and cl <= k:
                        V[n] = cl
                        T.append(n)
            Q = T
        return {a:b for a,b in V.items() if b != sys.maxsize}
    
    def findTheCity(self, N: int, E: List[List[int]], k: int) -> int:
        D = collections.defaultdict(list)
        
        for f,t,w in E:
            D[f].append((t, w))
            D[t].append((f, w))
        
        R = dict()
        mn = sys.maxsize
        for q in range(N):
            V = self.dfs(q, D, collections.defaultdict(lambda:sys.maxsize), k)
            R[q] = V
            if mn > len(V):
                mn = len(V)
            
        R = {a:b for a,b in R.items() if len(b) == mn}
        return max(R.keys())

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
        dp = [[float(\"inf\")] *n for _ in range(n)]
        
        for i,j,w in edges:
            dp[i][j] = dp[j][i] = w
            
        for i in range(n):
            dp[i][i] = 0
            
        for i in range(n):
            for j in range(n):
                for k in range(n):
                    dp[j][k] = min(dp[j][k] , dp[j][i] + dp[i][k])
                    
        res = { sum(d <= distanceThreshold for d in dp[i]) : i for i in range(n) }
        
        return res[min(res)]
    
        
        
        

'''
Idea is that we figure out for each city i all cities with index larger than i are reachable with distance at most distanceThreshold.
'''
import heapq
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        distances = defaultdict(dict)##will map for a vertex i to a dictionary containing key value pairs of the form j,distance, where distance from i to j is distance.
        edgeWeights = defaultdict(dict)
        for start,end,weight in edges:
            edgeWeights[start][end] = weight
            edgeWeights[end][start] = weight
        def computeDistances(i):##we will compute minimum distance for all vertices from i.
            iHeap = []
            heapq.heapify(iHeap)##remember you create list first and then heapify.
            heapq.heappush(iHeap,(0,i))
            visited = set()##need to ensure we don't go back and forth
            while iHeap:
                distance,vertex = heapq.heappop(iHeap)
                if vertex in visited:##don't want to expand a vertex if we already found its minimum distance
                    continue
                if distance > distanceThreshold:
                    break
                else:
                    distances[i][vertex] = distance##we know this vertex has to have closest distance to i
                    visited.add(vertex)##this is when we know we have found minimum distance
                    for neighbor in edgeWeights[vertex]:
                        if neighbor < i and i not in distances[neighbor]:##this means we already have that neighbor is not within a distance of i, so no chance. we can have neighbor appear in i.
                            continue
                        edgeWeight = edgeWeights[vertex][neighbor]
                        heapq.heappush(iHeap,(distance+edgeWeight,neighbor))
        lowestNumber = n
        lowestCity = -1
        for i in range(n):
            computeDistances(i)
            if len(distances[i]) <= lowestNumber:
                lowestNumber = len(distances[i])
                lowestCity = i
        ##print(distances)
        return lowestCity


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], limit: int) -> int:
        dist = [[float(\"inf\")]*n for _ in range(n)]
        for n1, n2, w in edges:
            dist[n1][n2] = w
            dist[n2][n1] = w
        
        for i in range(n):
            dist[i][i] = 0
        
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
        
        ans = {sum(dist[i][j] <= limit for j in range(n)):i for i in range(n)}
        return ans[min(ans)]
                            
            

from typing import List
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        city_dist_threshold = [float('inf')] * n
        dist_matrix = []

        for index in range(n):
            dist_matrix.append([float('inf')] * n)
        for i in range(n):
            dist_matrix[i][i] = 0

        for i,j,weight in edges:
            dist_matrix[i][j] = weight
            dist_matrix[j][i] = weight
        
        for k_index in range(n):
            for i_index in range(n):
                for j_index in range(n):
                    dist_matrix[i_index][j_index] = min(dist_matrix[i_index][j_index],  dist_matrix[i_index][k_index] + dist_matrix[k_index][j_index])
                    
        for i_index in range(n):
            for j_index in range(n):
                if dist_matrix[i_index][j_index] <= distanceThreshold:
                    if city_dist_threshold[i_index] == float('inf'):
                        city_dist_threshold[i_index] = 0
                    city_dist_threshold[i_index] += 1

        min_cities, city = min(city_dist_threshold), None
        for index in range(len(city_dist_threshold)):
            if city_dist_threshold[index] == min_cities:
                city = index
        

        return city

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        mark = [[float('inf') for i in range(n)] for j in range(n)]
        for i in range(n):
            mark[i][i]=0
        for i,j ,w in  edges:
            mark[i][j]=w
            mark[j][i]=w
        for node in range(n):
            for i in range(n):
                for j in range(n):
                    if i!=j:
                        mark[i][j] = min(mark[i][j],mark[i][node]+mark[node][j])
                    #if i==4 and j==0 and node==5:
                        #print(mark[i][node]+mark[node][j])
        #print(mark)
        cnt = n
        ans= -1
        for i in range(n):
            cur=0
            for j in range(n):
                if i!=j and mark[i][j]<=distanceThreshold:
                    cur+=1
            #print(cur)
            #print(cnt)
            if cur<=cnt: 
                #print(cur,cnt)
                cnt=cur
                ans= i
                #print(cur,cnt,ans)
        return ans


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], threshold: int) -> int:
        graph = defaultdict(list)
        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, w))
        
        def dijkstra(initial_node):
            dist = [float('inf')] * n
            dist[initial_node] = 0
            
            pq = [(initial_node, 0)]
            while pq:
                node, d = heappop(pq)
                
                for adjnode, weight in graph[node]:
                    if dist[adjnode] > dist[node] + weight:
                        dist[adjnode] = dist[node] + weight
                        pq.append((adjnode, dist[node]))
            return dist
        
        city_num = 0 # ans city number
        cc = n + 1 # cities connected
        for node in range(n):
            dist = dijkstra(node)
            print(dist)
            c = -1
            for d in dist:
                if d <= threshold:
                    c += 1

            if c <= cc:
                print(c)
                cc = c
                city_num = node

        return city_num


import math

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        distance=[[math.inf for i in range(n)] for j in range(n)]
        for i in edges:
            distance[i[0]][i[1]]=i[2]
            distance[i[1]][i[0]]=i[2]
            
        for i in range(n):
            for j in range(n):
                if i!=j and distance[i][j]!=math.inf:
                    for k in range(n):
                        if k!=i:
                            d=distance[i][j]+distance[j][k]
                            if d<distance[i][k]:
                                distance[i][k]=d
                                # print(i,j,k)
                                # print(\"\
\")
                            
        for i in range(n):
            for j in range(n):
                if i!=j and distance[i][j]!=math.inf:
                    for k in range(n):
                        if k!=i:
                            d=distance[i][j]+distance[j][k]
                            if d<distance[i][k]:
                                distance[i][k]=d
                                
        # print(distance)
        mini=math.inf
        for i in range(n):
            a=0
            for j in range(n):
                if distance[i][j]<=distanceThreshold:
                    a+=1
            # print(a)
            if a<=mini:
                mini=a
                city=i
                
        return city

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
        dist = [[float('inf')] * n for _ in range(n)]
        for i in range(n):
            dist[i][i] = 0
        for pair in edges:
            a, b, c = pair
            dist[a][b] = dist[b][a] = c
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
                        
        res = {}
        
        for i in range(len(dist)):
            res[sum(x <= distanceThreshold for x in dist[i])] = i
        
        return res[min(res)]

class Solution:
    \"\"\"
    Floyd-Warshall
    \"\"\"
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        dp = [[float('inf')]*n for _ in range(n)]
        for i in range(n):
            dp[i][i] = 0
        
        for u, v, w in edges:
            dp[u][v] = w
            dp[v][u] = w
        
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if i == k or j == k:
                        continue
                    dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])
        
        min_city = n-1
        min_reachable = float('inf')
        for i in range(n):
            reachable = sum([dp[i][dst] <= distanceThreshold for dst in range(n)])
            if reachable <= min_reachable:
                min_city = i
                min_reachable = reachable
        
        return min_city

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        import numpy
        adj = [[float('inf')]*n for _ in range(n)]
        
        for u, v, w in edges:
            adj[u][v] = adj[v][u] = w
            
        for i in range(n):
            adj[i][i] = 0
        
            
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j])
        print(numpy.matrix(adj))                  
        

        res = {sum(d <= distanceThreshold for d in adj[i]): i for i in range(n)}
        print(res)
        return res[min(res)]

import collections
from heapq import heappop,heappush
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
        dist=[[float('inf') for _ in range(n)] for _ in range(n)]
        graph=collections.defaultdict(list)
        
        for u,v,w in edges:
            dist[u][v]=dist[v][u]=w
            graph[u].append(v)
            graph[v].append(u)
        for i in range(n):
            dist[i][i]=0
        visited=set()
        
        for i in range(n):
            stack=[(0,i)]
            while stack:
                k,j=heappop(stack)
                if (i,j) not in visited and k<=distanceThreshold:
                    visited.add((i,j))
                    for neigh in graph[j]:
                        dist[i][neigh]=min(dist[i][neigh],k+dist[j][neigh])
                        heappush(stack,(dist[i][neigh],neigh))
        print(dist)
        ans=None
        maxi=float('inf')
        for i in range(n):
            temp=0
            for j in range(n):
                if dist[i][j]<=distanceThreshold:
                    temp+=1
            if temp<=maxi:
                maxi=temp
                ans=i
        return ans

class Solution:
    def findTheCity(self, n: int, edges, distanceThreshold: int) -> int:
        matrix = [[float('inf')]*n for _ in range(n)]
        for s, e, d in edges:
            matrix[s][e] = d
            matrix[e][s] = d
        for i in range(n):
            matrix[i][i] = 0
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    matrix[i][j] = min(matrix[i][j], matrix[i][k]+matrix[k][j])
        res, count = 0, n
        for i in range(n):
            tmp = sum(matrix[i][j] <= distanceThreshold for j in range(n))
            if tmp <= count:
                count = tmp
                res = i
        return res

from heapq import heappush, heappop
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        dis = [[float('inf')]*n for _ in range(n)]
        nei = collections.defaultdict(list)
        for i,j,x in edges:
            dis[i][j] = dis[j][i] = x
            nei[i].append(j)
            nei[j].append(i)
        for i in range(n):
            dis[i][i] = 0
        
        # Dijkstra
        visited = set()
        for i in range(n):
            pool = [(0,i)]                                          # pool[j] = x:  d(i,j) = x    
            while pool:
                x,j = heappop(pool)                                 # x = d(i,j)
                if (i,j) not in visited and x <= distanceThreshold: # early stop, if distance exceeds threshold
                    visited.add((i,j))
                    for k in nei[j]:
                        dis[i][k] = min(dis[i][k], x+dis[j][k])     # dis(i,k) = min(dis(i,k), dis(i,j)+dis(j,k))
                        heappush(pool, (dis[i][k], k))

        cities = {sum(d <= distanceThreshold for d in dis[i]):i for i in range(n)}
        return cities[min(cities)]

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        minDistance = collections.defaultdict(lambda: collections.defaultdict(lambda: math.inf))
        for i in range(n):
            minDistance[i][i] = 0
        
        for u, v, weight in edges:
            minDistance[u][v] = weight
            minDistance[v][u] = weight
        
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    minDistance[i][j] = min(minDistance[i][j], minDistance[i][k] + minDistance[k][j])
        
        minNeighborCount = math.inf
        minCity = -1
        
        for i in range(n):
            # Count how many of city i's neighbors are within the distance threshold.
            neighborCount = sum(minDistance[i][j] <= distanceThreshold for j in range(n) if j != i)
            
            # Update the result if a city with less neighbors has been found or the id is higher
            if neighborCount <= minNeighborCount:
                minNeighborCount = neighborCount
                minCity = i
        
        return minCity

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        storage = [[30000 if i != j else 0 for i in range(n) ] for j in range(n)]
        for edge in edges:
            storage[edge[0]][edge[1]] = edge[2]
            storage[edge[1]][edge[0]] = edge[2]
        
        #FloydWarshallAPSP
        for k in range(0, n):
            for i in range(0, n):
                for j in range(0, n):
                    currD = storage[i][j]
                    toK = storage[i][k]
                    fromK = storage[k][j]
                    storage[i][j] = min(storage[i][j], toK + fromK)
                    
        print(\"storage\", storage)
        
        #Process to get answer
        numCities = [0 for i in range(n)]
        currLowestCity = 0
        currLowestCount = 200
        for i in range(0, n):
            count = 0
            for j in range(0, n):
                if storage[j][i] <= distanceThreshold:
                    count += 1
            if count <= currLowestCount:
                currLowestCity = i
                currLowestCount = count
        
        return currLowestCity


from heapq import heappush, heappop
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        dis = [[float('inf')]*n for _ in range(n)]
        nei = collections.defaultdict(list)
        for i,j,x in edges:
            dis[i][j] = dis[j][i] = x
            nei[i].append(j)
            nei[j].append(i)
        for i in range(n):
            dis[i][i] = 0
        
        # Dijkstra
        visited = set()
        for i in range(n):
            pool = [(0,i)]                                          # pool[j] = x:  d(i,j) = x    
            while pool:
                x,j = heappop(pool)                                 # x = d(i,j)
                if (i,j) not in visited and x <= distanceThreshold: # early stop, if distance exceeds threshold
                    visited.add((i,j))
                    for k in nei[j]:
                        dis[i][k] = min(dis[i][k], x+dis[j][k])     # dis(i,k) = min(dis(i,k), dis(i,j)+dis(j,k))
                        heappush(pool, (dis[i][k], k))

        cities = {sum(d <= distanceThreshold for d in dis[i]):i for i in range(n)}
        print(cities)
        return cities[min(cities)]

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        distance = [[float('inf') for _ in range(n)] for _ in range(n)]
        
        for i, j, w in edges:
            distance[i][j] = w
            distance[j][i] = w
        
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
        
        m = collections.defaultdict()
        ans = 0
        
        print(distance)
        
        for i in range(n):
            temp = 0
            for j in range(n):
                if distance[i][j] <= distanceThreshold and i != j:
                    temp += 1
            m[temp] = i
        print(m)
        return m[min(m.keys())]

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], threshold: int) -> int:
        graph = collections.defaultdict(list)
        res = [0] * n
        for a, b, d in edges:
            graph[a].append([b, d])
            graph[b].append([a, d])
        for i in range(n):
            queue = [[0, i]]
            visit = set()
            while queue:
                t, curr = heapq.heappop(queue)
                if t <= threshold and curr not in visit:
                    visit.add(curr)
                    for nei, dis in graph[curr]:
                        heapq.heappush(queue, [t + dis, nei])    
            res[i] = len(visit) - 1
        return -sorted([[v, -i] for i, v in enumerate(res)])[0][1]

import itertools as it


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        inf = float(\"inf\")
        dp = [[inf] * n for _ in range(n)]
        
        for i in range(n):
            dp[i][i] = 0
        
        for a, b, w in edges:
            dp[a][b] = min(dp[a][b], w)
            dp[b][a] = min(dp[b][a], w)
            
        for k, j , i in it.permutations(range(n), 3):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
            dp[j][i] = dp[i][j]
            
        out = min([(sum(1 for r in row if r <= distanceThreshold), -i) for i, row in enumerate(dp)])
        
        return -out[1]
        

from collections import defaultdict
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], cap: int) -> int:
        
        minDistance = collections.defaultdict(lambda: collections.defaultdict(lambda: float(\"inf\")))
        
        for i in range(n):
            minDistance[i][i]=0
        
        for i,j,w in edges:
            minDistance[i][j]=w
            minDistance[j][i]=w
        
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    minDistance[i][j]=min(minDistance[i][j],minDistance[i][k]+minDistance[k][j])
        
        mi=float(\"inf\")
        ans=-1
        
        for i in range(n):
            neighCount=sum(minDistance[i][j]<=cap for j in range(n) if j!=i)
            if(neighCount<=mi):
                mi=neighCount
                ans=i
        return ans
        
        
        
        
        
        
        
        
        
        
        
#         graph=defaultdict(list)
        
#         for i in edges:
#             graph[i[0]].append([i[1],i[2]])
#             graph[i[1]].append([i[0],i[2]])
            
#         # print(graph)
#         self.ans=-1
#         self.mi=float('inf')
#         def bfs(parent):
#             seen={parent:-1}
#             q=[(parent,0)]
#             while(q!=[]):
#                 tem_node,used=q.pop(0)
#                 for node,dist in graph[tem_node]:
#                     if((node not in seen or dist+used<seen[node]) and (dist+used)<=cap):
#                         q.append((node,dist+used))
#                         seen[node]=dist+used
#             if(self.mi>len(seen)):
#                 self.mi=len(seen)
#                 self.ans=parent
#             elif(self.mi==len(seen) and parent>self.ans):
#                 self.ans=parent
        
#         for i in range(n):
#             bfs(i)
            
#         return self.ans
        
        
        
        
        
#         di=dict()
#         for i in range(n):
#             di[i]=set()
        
#         print(graph)
#         # self.mi=float('inf')
#         # self.node=-1
#         def dfs(node,thres,covered,parent):
#             if(thres<0):
#                 return
#             di[parent].add(node)
#             for i in graph[node]:
#                 dfs(i[0],thres-i[1],covered+1,parent)
            
        
#         for i in range(n):
#             dfs(i,distanceThreshold,0,i)
#         ans=-1
#         mi=float('inf')
#         print(di)
#         for i,j in di.items():
#             if(len(j)-1<mi):
#                 mi=len(j)-1
#                 ans=i
#             elif(len(j)-1==mi):
#                 ans=i
#         return ans
        
        
        # return self.node

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
        dis = [[float('inf')] * n for _ in range(n)]
        for i, j, w in edges:
            dis[i][j] = dis[j][i] = w
        for i in range(n):
            dis[i][i] = 0
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
        res = {sum(d <= distanceThreshold for d in dis[i]): i for i in range(n)}
        return res[min(res)]

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        A = []
        for i in range(n):
            A.append([float('inf')]*n)
        for i in range(len(A)):
            A[i][i] = 0                    
        for i in edges:
            A[i[0]][i[1]] = i[2]
            A[i[1]][i[0]] = i[2]
        for k in range(n):
            for i in range(len(A)):
                for j in range(len(A[i])):
                    if i == j or i == k or j == k:
                        continue
                    A[i][j] = min(A[i][j],A[i][k]+A[k][j])
        print(A)
        minc = float('inf')
        city = n-1
        for i in range(len(A)):
            cnt = 0
            for j in range(len(A[i])):
                if A[i][j] <= distanceThreshold:
                    cnt += 1
            if cnt <= minc:
                minc = cnt
                city = i
        return city


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], threeshold: int) -> int:
        class Graph:
            def __init__(self,vertices):
                self.v = vertices
                self.graph = collections.defaultdict(dict)

            def add_edge(self,u,v,cost):
                self.graph[u][v] = cost
                self.graph[v][u] = cost

            def calculateDist(self,s,dT):
                dist = [sys.maxsize]*(self.v)
                dist[s] = 0
                unvisited_queue = [[0,s]]
                visited = [False]*self.v
                heapq.heapify(unvisited_queue)
                while len(unvisited_queue) > 0:
                    u =  heapq.heappop(unvisited_queue)
                    curr_v = u[1]
                    visited[curr_v] = True
                    for neighbour in self.graph[curr_v]:
                        cost = self.graph[curr_v][neighbour]
                        if dist[neighbour] > dist[curr_v] + cost:
                            dist[neighbour] = dist[curr_v] + cost
                    while len(unvisited_queue) > 0:
                        heapq.heappop(unvisited_queue)
                    for node in range(self.v):
                        if visited[node] == False:
                            heapq.heappush(unvisited_queue,[dist[node],node])
                cities = -1
                for d in dist:
                    if d <= dT:
                        cities += 1
                return cities
        min_connections = sys.maxsize
        city = 0
        v = n
        graph = Graph(v)
        for edge in edges:
            n,m,cost = edge[0],edge[1],edge[2]
            graph.add_edge(n,m,cost)
        # print(graph.graph)
        for i in range(v):
            cities = graph.calculateDist(i,threeshold)
            if cities < min_connections:
                min_connections = cities
                city = i
            elif cities == min_connections:
                city = max(city,i)
        return city

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        # Start at 11:09PM
        # Brute force: O(N*(N + E))
        
        # Need to make a dictionary holding the edges
        edges_dict= collections.defaultdict(list)
        for src,dest,weight in edges:
            edges_dict[src].append((dest, weight))
            edges_dict[dest].append((src, weight))
        
        # Helper function 
        # Gets input as the node to start from, and distance that can be travelled
        # returns count of nodes that it can reach
        
        import heapq
        # Need to do book keeping, if can reach given node quicker
        def get_reachable_count(nd, distance):
            heap = [(0, nd)]
            count = 0
            visited = set()
            while heap:
                travelled, nd = heapq.heappop(heap)
                if nd in visited:
                    continue
                
                visited.add(nd)
                count += 1
                for (dest, new_dist) in edges_dict[nd]:
                    if new_dist + travelled > distance or dest in visited:
                        continue
                    heapq.heappush(heap, (new_dist+travelled, dest))
            return count - 1
        get_reachable_count(1, distanceThreshold)
        curr_min_val = float('inf')
        curr_best_idx = -1
        for i in range(n):
            count = get_reachable_count(i, distanceThreshold) 
            # print(\"Fin\", i, count)
            if count <= curr_min_val:
                curr_min_val, curr_best_idx = count, i
        return curr_best_idx
                
                


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        from heapq import heappush, heappop
        import collections
        distance = [[float('inf')] * n for _ in range(n)]
        graph = collections.defaultdict(list);
        # initialize the graph and distance matrix
        for i, j, w in edges:
            distance[i][j] = distance[j][i] = w
            graph[i].append(j)
            graph[j].append(i)
        for i in range(n):
            distance[i][i] = 0
        
        # use dijkstra algorithm for every node
        global_min = [-1, -1]
        for i in range(n):
            count = 0
            visited = set()
            q = [(0, i)]
            while q:
                dis, j = heappop(q)
                if dis <= distanceThreshold:
                    count += 1
                if (i, j) not in visited and dis < distanceThreshold:
                    visited.add((i, j))
                    for nei in graph[j]:
                        distance[i][nei] = min(distance[i][nei], dis + distance[j][nei])
                        heappush(q, (distance[i][nei], nei))
        global_min = [-1, -1]
        for i in range(n):
            count = 0
            for j in range(n):
                if distance[i][j] <= distanceThreshold:
                    count += 1
                
            if global_min[0] == -1 or count <= global_min[0]:
                global_min[0] = count
                global_min[1] = i
        
        return global_min[1]


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        dis = [[float(\"inf\") ] * n for _ in range(n)]
        for i in range(n):
            dis[i][i] = 0
        for u, v, w in edges:
            dis[u][v] = dis[v][u] = w
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
        res = -1
        min_count = float(\"inf\")
        for k in range(n-1, -1, -1):
            count = 0
            for j in range(n):
                if dis[k][j] <= distanceThreshold:
                    count += 1
            if min_count > count:
                res = k
                min_count = count
        return res

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        from heapq import heappush, heappop
        import collections
        distance = [[float('inf')] * n for _ in range(n)]
        graph = collections.defaultdict(list);
        # initialize the graph and distance matrix
        for i, j, w in edges:
            distance[i][j] = distance[j][i] = w
            graph[i].append(j)
            graph[j].append(i)
        for i in range(n):
            distance[i][i] = 0
        
        # use dijkstra algorithm for every node
        global_min = [-1, -1]
        for i in range(n):
            count = set()
            visited = set()
            q = [(0, i)]
            while q:
                dis, j = heappop(q)
                if dis <= distanceThreshold:
                    count.add(j)
                if (i, j) not in visited and dis < distanceThreshold:
                    visited.add((i, j))
                    for nei in graph[j]:
                        distance[i][nei] = min(distance[i][nei], dis + distance[j][nei])
                        heappush(q, (distance[i][nei], nei))
            # print(count)
            if global_min[0] == -1 or len(count) <= global_min[0]:
                global_min[0] = len(count)
                global_min[1] = i
        
        return global_min[1]


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        graph = defaultdict(list)
        output = []
        
        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, w))
        
        queue = deque([])
        for i in range(n):
            
            #distance , node
            queue.append((i, 0))
            
            # current represent a hash map of all of the cities and 
            # their distances from i
            curr = {}
            
            while queue:
                node, dist = queue.popleft()
                
                if node in curr and dist >= curr[node]:
                    continue
                
                curr[node] = dist
                
                for nei, newDist in graph[node]:
                    if newDist + dist <= distanceThreshold:
                        queue.append((nei, newDist + dist))
            
            output.append(len(curr)-1)
            # print(output)
        
        for node in reversed(range(len(output))):
            if output[node] == min(output):
                return node

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        dp = [[10001 for j in range(n)] for i in range(n)]
        for i in range(n):
            dp[i][i] = 0
        
        for u, v, w in edges:
            dp[u][v] = w
            dp[v][u] = w
        
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
        
        l = []
        smallest = 101
        for i in range(n):
            temp = 0
            for j in range(n):
                if dp[i][j] <= distanceThreshold:
                    temp += 1
                
            if temp < smallest:
                smallest = temp
                l = [i]
            elif temp == smallest:
                l.append(i)
        
        return l[-1]


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        dis = [[float('inf')]*n for _ in range(n)]
        nei = collections.defaultdict(list)
        for i,j,x in edges:
            dis[i][j] = dis[j][i] = x
            nei[i].append(j)
            nei[j].append(i)
        for i in range(n):
            dis[i][i] = 0
        
        # Dijkstra
        visited = set()
        for i in range(n):
            pool = [(0,i)] 
            while pool:
                x,j = heapq.heappop(pool)
                if (i,j) not in visited and x <= distanceThreshold:
                    visited.add((i,j))
                    for k in nei[j]:
                        dis[i][k] = min(dis[i][k], x+dis[j][k])
                        heapq.heappush(pool, (dis[i][k], k))

        cities = {sum(d <= distanceThreshold for d in dis[i]):i for i in range(n)}
        return cities[min(cities)]

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        mat=[]
        for _ in range(n):
            mat.append([float('inf')]*n)
            
        for i,j,d in edges:
            mat[i][j]=d
            mat[j][i]=d
        
        for i in range(n):
            mat[i][i]=0
            
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    mat[i][j]=min(mat[i][j],mat[i][k]+mat[k][j])
        
        res=[]
        for i in range(n):
            res.append(sum(1 for x in mat[i] if x<=distanceThreshold))
        
        s=float('inf')
        for i in range(n):
            if res[i] <=s:
                s=res[i]
                out=i
                
        return out

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        dis = [[float('inf')]*n for _ in range(n)]
        nei = collections.defaultdict(list)
        for i,j,x in edges:
            dis[i][j] = dis[j][i] = x
            nei[i].append(j)
            nei[j].append(i)
        for i in range(n):
            dis[i][i] = 0
        
        # Dijkstra
        visited = set()
        for i in range(n):
            pool = [(0,i)]                                          # pool[j] = x:  d(i,j) = x    
            while pool:
                x,j = heapq.heappop(pool)                                 # x = d(i,j)
                if (i,j) not in visited and x <= distanceThreshold: # early stop, if distance exceeds threshold
                    visited.add((i,j))
                    for k in nei[j]:
                        dis[i][k] = min(dis[i][k], x+dis[j][k])     # dis(i,k) = min(dis(i,k), dis(i,j)+dis(j,k))
                        heapq.heappush(pool, (dis[i][k], k))

        cities = {sum(d <= distanceThreshold for d in dis[i]):i for i in range(n)}
        return cities[min(cities)]

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        A = [[float('inf')]*n for _ in range(n)]
        for i in range(n):
            A[i][i] = 0
        for x, y, w in edges:
            A[x][y] = w
            A[y][x] = w
            
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    A[i][j] = min(A[i][j], A[i][k] + A[k][j])
                
        res = -1        
        val = float('inf')
        for i in range(n):
            t = sum([d <= distanceThreshold for d in A[i]])
            if t <= val:
                val = t
                res = i
        return res

from heapq import heappush, heappop
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
        def dijkstra(graph, start, distance):
            reached = set()
            heap = [(0, start)]
            while heap:
                w, node = heappop(heap)
                if node in reached:
                    continue
                if w > distance:
                    continue
                if node != start:
                    reached.add(node)
                for nex, nex_w in graph[node]:
                    heappush(heap, (w + nex_w, nex))
            return len(reached)
        
        graph = collections.defaultdict(set)        
        for x,y,w in edges:
            graph[x].add((y,w))
            graph[y].add((x,w))
        
        min_len = n
        min_city = 0
        for i in range(n):
            reached = dijkstra(graph, i, distanceThreshold)
            if reached <= min_len:
                min_len = reached
                min_city = i
        return min_city
        


class Solution:
    def visitedAllNodes(self, src, graph, n, max_d):
        visited = [False for i in range(n)]
        heap = [(0, src)]
        
        while heap:
            d, node  = heapq.heappop(heap)
            if not visited[node]:
                visited[node] = True
                for neighbor,w in graph[node]:
                    if d+w <= max_d and not visited[neighbor]:
                        heapq.heappush(heap, (d+w, neighbor))
                        
            
        return sum(visited)
        
        
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        graph = collections.defaultdict(list)
        node, nodes_reached = -1, n+1
        for i,j,w in edges:
            graph[i].append((j,w))
            graph[j].append((i,w))
            
        for i in range(n):
            count = self.visitedAllNodes(i, graph, n, distanceThreshold)
            if count <= nodes_reached:
                node = i
                nodes_reached = count
        return node
            


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        adjl = [[] for _ in range(n)]
        d = distanceThreshold
        for e in edges:
            i, j, w = e
            adjl[i].append((w, j))
            adjl[j].append((w, i))
        inf = float('inf')
        minc = 1e9
        mini = 0
        for i in range(n):
            ds = [inf for _ in range(n)]
            ds[i] = 0
            fringe = [(e[0], (i, e[1])) for e in adjl[i]]
            heapq.heapify(fringe)
            visited = {i}
            while len(fringe) > 0:
                w, uv = heapq.heappop(fringe)
                u, v = uv
                if w > d:
                    continue
                if v not in visited:
                    ds[v] = min(ds[v], w)
                    for e in adjl[v]:
                        heapq.heappush(fringe, (e[0] + ds[v], (v, e[1])))
                    visited.add(v)
            cnt = len([c for c in ds if c <= d])
            if cnt <= minc:
                minc = cnt
                mini = i
        return mini


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
        distance = [[float(\"inf\")] * n for i in range(n)]
        
        for city_1, city_2, weight in edges:
            
            distance[city_1][city_2] = weight
            distance[city_2][city_1] = weight
            
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    
                    if i == j:
                        continue
                    
                    distance[i][j] = min(distance[i][k] + distance[k][j], distance[i][j])
                    distance[j][i] = distance[i][j]
                            
        counts = []
        for i in range(n):
            
            within_threshold = 0
            for j in range(n):
                
                if distance[i][j] <= distanceThreshold:
                    within_threshold += 1
                    
            counts.append(within_threshold)
                        
        minimum_city_index = -1
        minimum_city_distance = float(\"inf\")
        for i in range(n):
            
            if counts[i] <= minimum_city_distance:
                
                minimum_city_index = i
                minimum_city_distance = counts[i]
                
        return minimum_city_index
            
            

import heapq
class Solution:
  # return number of nodes reachable
  def shortestPath(self, root, graph, distanceThreshold):
    
    # shortest distance to root
    dist = {}
    dist[root] = 0
    visited = set()
    # [(dist, root)]
    queue = [(0, root)]
    count = 0
    while queue:
      pickDist, pick = heapq.heappop(queue)
      if pick in visited:
        continue
      visited.add(pick)
      if pickDist <= distanceThreshold:
        count += 1
      else:
        continue
      for neighbor, weight in graph[pick]:
        dist[neighbor] = min(dist.get(neighbor, float('inf')), pickDist + weight)
        heapq.heappush(queue, (dist[neighbor], neighbor))
    
    return count
    
  def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
    # node from 0 to n-1
    # multiple undirected graphs?
  
    # construct graph: node -> [(node, weight)]
    graph = {k: [] for k in range(n)}
    for u, v, w in edges:
      graph[u].append((v, w))
      graph[v].append((u, w))
    
    minReachableCount = float('inf')
    ans = 0
    # for every node, run dijkastra algorithm, stop when the threshold is reached
    for i in range(n):
      reachCount = self.shortestPath(i, graph, distanceThreshold)
      if reachCount <= minReachableCount:
        minReachableCount = reachCount
        ans = i
        
    return ans


from collections import defaultdict
import heapq
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        results = []
        graph = defaultdict(dict)
        for x, y, dist in edges:
            graph[x][y] = dist
            graph[y][x] = dist
        for i in range(n):
            results.append(self.traverse(graph, distanceThreshold, i, n))
        min_result = min(results)
        for i in range(n-1, -1, -1):
            if results[i] == min_result:
                return i
        return 
    
    def traverse(self, graph, threshold, start, n):
        q = [[start, 0]]
        count = 0
        distances = [float('inf')] * n
        distances[start] = 0
        while q:
            city, dist = heapq.heappop(q)
            for key in list(graph[city].keys()):
                new_dist = dist + graph[city][key]
                if distances[key] > new_dist:
                    distances[key] = new_dist
                    heapq.heappush(q, [key, dist + graph[city][key]])
        count = sum([1 for x in distances if x <= threshold])
        return count - 1
                    
        


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
        from heapq import heappush, heappop
        
        dis = [[float('inf')]*n for _ in range(n)]
        nei = collections.defaultdict(list)
        for i,j,x in edges:
            dis[i][j] = dis[j][i] = x
            nei[i].append(j)
            nei[j].append(i)
        for i in range(n):
            dis[i][i] = 0
        
        # Dijkstra
        visited = set()
        for i in range(n):
            pool = [(0,i)]                                          # pool[j] = x:  d(i,j) = x    
            while pool:
                x,j = heappop(pool)                                 # x = d(i,j)
                if (i,j) not in visited and x <= distanceThreshold: # early stop, if distance exceeds threshold
                    visited.add((i,j))
                    for k in nei[j]:
                        dis[i][k] = min(dis[i][k], x+dis[j][k])     # dis(i,k) = min(dis(i,k), dis(i,j)+dis(j,k))
                        heappush(pool, (dis[i][k], k))
        globalMin = [-1, -1]
        for i in range(n):
            total = 0
            for j in range(n):
                if dis[i][j] <= distanceThreshold:
                    total += 1
            if globalMin[0] == -1 or total <= globalMin[0]:
                globalMin[0] = total
                globalMin[1] = i
        return globalMin[1]


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        dist = [[math.inf] * n for i in range(n)]
        
        for e in edges:
            dist[e[0]][e[1]] = e[2]
            dist[e[1]][e[0]] = e[2]
            
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        
        print(dist)
        
        max_city_numbers = n+1
        selected_city = n
        for i in range(n-1, -1, -1):
            city_numbers = 0
            for j in range(n):
                if i != j and dist[i][j] <= distanceThreshold:
                    city_numbers += 1
            print(city_numbers)
            if city_numbers < max_city_numbers:
                max_city_numbers = city_numbers
                selected_city = i
                
        return selected_city

from heapq import heappush, heappop
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
        def dijkstra(graph, start, distance):
            reached = set()
            heap = [(0, start)]
            while heap:
                w, node = heappop(heap)
                if node in reached:
                    continue
                if w > distance:
                    continue
                if node != start:
                    reached.add(node)
                for nex, nex_w in graph[node]:
                    heappush(heap, (w + nex_w, nex))
            return reached
        
        graph = collections.defaultdict(set)        
        for x,y,w in edges:
            graph[x].add((y,w))
            graph[y].add((x,w))
        
        min_len = n
        min_city = 0
        for i in range(n):
            reached = dijkstra(graph, i, distanceThreshold)
            if len(reached) <= min_len:
                min_len = len(reached)
                min_city = i
        return min_city
        


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        dp = [[float(inf)] * n for _ in range(n)]
        
        for a,b, cost in edges:
            dp[a][b] = cost
            dp[b][a] = cost
        
        for i in range(n):
            dp[i][i] = 0
        
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

        idx = 0
        m = len([e for e in dp[0] if e <= distanceThreshold])
        for i in range(1,n):
            l = len([e for e in dp[i] if e <= distanceThreshold])
            if l <= m:
                m = l
                idx = i
        return idx


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        graph = [[float('inf') for _ in range(n)] for _ in range(n)]
        for v1, v2, w in edges:
            graph[v1][v2] = w
            graph[v2][v1] = w
        for i in range(n):
            graph[i][i] = 0
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
        
        # print(graph)
        
        currmin = float('inf')
        currv = -1
        for i in range(n):
            curr = 0
            for j in range(n):
                if graph[i][j] <= distanceThreshold:
                    curr += 1
                    if curr > currmin:
                        break
            if curr <= currmin:
                # print(i, curr)
                currmin = curr
                currv = i
        return currv
                    
        
                
                
            





from heapq import *
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:

        def find_n_neigh(source_city):

            visited = set()
            pq = [(0, source_city)]

            while pq:

                trav_dist, curr_city = heappop(pq)

                if curr_city in visited:
                    continue

                if curr_city != source_city:
                    visited.add(curr_city)

                for neigh, distance in graph[curr_city]:
                    if neigh not in visited and trav_dist + distance <= distanceThreshold:
                        heappush(pq, (trav_dist + distance, neigh))

            return len(visited)


        graph = defaultdict(list)
        for city, neigh, distance in edges:
            graph[city].append((neigh, distance))
            graph[neigh].append((city, distance))

        n_neighs = [find_n_neigh(city) for city in range(n)]
        min_n = min(n_neighs)
        return [city for city in range(n) if n_neighs[city] == min_n][-1]




class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:

        graph = defaultdict(list)
        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, w))
         
        
        output = []
        queue = deque([])
        
        for i in range(n):
            
            queue.append((i, 0))
            curr = {}
            
            while queue:
                
                node, dist = queue.popleft()
                
                if node in curr and dist >= curr[node]:
                    continue
                
                curr[node] = dist
                
                for nei, newDist in graph[node]:
                    if dist + newDist <= distanceThreshold:
                        queue.append((nei, dist + newDist))
                        
            output.append(len(curr) -1)
            
        for node in reversed(range(len(output))):
            if output[node] == min(output):
                return node

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        # matrices
        # for i,j,k
        # min value
        matrix = [[float('inf') for x in range(n)] for y in range(n)]
        
        # build initial matrix
        for i in range(n):
            matrix[i][i] = 0
                    
        for u,v,w in edges:
            matrix[u][v] = w
            matrix[v][u] = w

        
        print(matrix)

        
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    matrix[i][j] = min(matrix[i][j], matrix[i][k]+matrix[k][j])

        print(matrix)
        res = defaultdict(int)
        for i, row in enumerate(matrix):
            for j, dist in enumerate(row):
                if dist <= distanceThreshold and i != j :
                    res[i] += 1
        
        # check if unconnected cities
        unconnected = []
        i = 0
        while i < n:
            if res[i] == 0:
                # not conencted
                unconnected.append(i)
            i += 1
                
        if len(unconnected) == 1:
            return unconnected[0]
        elif len(unconnected) > 1:
            return max(unconnected)
            
        
        ans = min(res.values())
        max_city = 0
        
        for city in range(len(res)):
            if res[city] <= ans and city > max_city:
                max_city = city
                
        print(res)
        print(ans)
        print(max_city)
        return max_city

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        graph = defaultdict(list)
        result = {} 

        # build the adjacency list
        for edge in edges:
            src = edge[0]
            dest = edge[1]
            cost = edge[2]

            graph[src].append((dest, cost))
            graph[dest].append((src, cost))

        # {0: [(1, 3)], 1: [(2, 1), (3, 4)], 2: [(3, 1)]}
        # get the number of vertices that can be reached starting from vertex i. Also, the vertices
        # that can be reached should have a distance below the threshold.
        for i in range(n): # 0
            num_vertices = self.get_num_vertices_less_than_threshold(graph, i, distanceThreshold) # g, 0, 4
            result[i] = num_vertices
        
        # pprint.pprint(result)
        min_vertex_val = min(result.values())
        # pprint.pprint(min_vertex_val)

        index = list([-1 if x[1] != min_vertex_val else x[0] for x in list(result.items())])

        # pprint.pprint(index)

        # min_vertex = sorted(result.items(), key=lambda x: x[1])
        # pprint.pprint(min_vertex)

        return max(index)
    
    def get_num_vertices_less_than_threshold(self, graph, vertex, thresh): # g, 0, 4
        queue = [] 
        queue.append((0, vertex)) # (0, 0) 
        reachable_nodes = [] # []

        while queue: # (3, 1)
            dist, node = heapq.heappop(queue) # 3, 1

            if node in reachable_nodes:
                continue
            
            reachable_nodes.append(node) # [0, 1]

            for vert in graph[node]: # (2, 1), (3, 4)
                neigh_vert = vert[0] # 2
                neigh_cost = vert[1] # 1

                if dist + neigh_cost <= thresh: # 3 + 1 <= 4
                    heapq.heappush(queue, (dist + neigh_cost, neigh_vert)) # [(4, 1)]

        return len(reachable_nodes) - 1 


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        dp = [[sys.maxsize for _ in range(n)] for _ in range(n)] 
        for s, e, w in edges:
            dp[s][e] = w
            dp[e][s] = w
            
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if dp[i][k]!=sys.maxsize and dp[j][k]!=sys.maxsize:
                        dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])
        result = [0 for i in range(n)]
        for i in range(n):
            for j in range(i+1, n):
                if dp[i][j]<=distanceThreshold:
                    result[i]+=1
                    result[j]+=1
        # print(result)        
        return min([(i, val) for i, val in enumerate(result)], key=lambda x: (x[1], -x[0]))[0]            

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        dist = [[math.inf] * n for i in range(n)]
        
        for e in edges:
            dist[e[0]][e[1]] = e[2]
            dist[e[1]][e[0]] = e[2]
            
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        
        
        max_city_numbers = n+1
        selected_city = n
        for i in range(n-1, -1, -1):
            city_numbers = 0
            for j in range(n):
                if i != j and dist[i][j] <= distanceThreshold:
                    city_numbers += 1
            
            if city_numbers < max_city_numbers:
                max_city_numbers = city_numbers
                selected_city = i
                
        return selected_city

import gc
from collections import defaultdict
gc.disable()
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        graph = [[math.inf for _ in range(n)] for _ in range(n)]
        for source, sink, cost in edges:
            graph[source][sink] = cost
            graph[sink][source] = cost
        for k in range(n):
            for i in range(n):
                if i == k: continue
                for j in range(n):
                    if i == j or j == k: continue
                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
        counts_map = defaultdict(lambda: -1)
        for i in range(n):
            count = 0
            for x in graph[i]:
                if x <= distanceThreshold: count += 1
            counts_map[count] = max(counts_map[count], i)
        return counts_map[min(counts_map.keys())]


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        graph = [[float('inf') for _ in range(n)] for _ in range(n)]
        for v1, v2, w in edges:
            graph[v1][v2] = w
            graph[v2][v1] = w
        for i in range(n):
            graph[i][i] = 0
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
        
        print(graph)
        
        currmin = float('inf')
        currv = -1
        for i in range(n):
            curr = 0
            for j in range(n):
                if graph[i][j] <= distanceThreshold:
                    curr += 1
                    if curr > currmin:
                        break
            if curr <= currmin:
                # print(i, curr)
                currmin = curr
                currv = i
        return currv
                    
        
                
                
            


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        def BFS(queue):
            while queue:
                route , wt = queue.popleft()
                for node , node_wt in d[route]:
                    if min_wt[node] > node_wt + wt:
                        queue.append([node , node_wt + wt])
                        min_wt[node] = node_wt + wt
            return min_wt
        d , seen ,ans , m = defaultdict(list) , set()  , [] , inf
        for x , y , z in edges:d[x] += [[y,z]];d[y] += [[x,z]]
        for i in range(n):
            min_wt = [inf]*(n)
            ans.append(BFS(deque([[i,0]])))
            min_wt[i] = inf
        res = 0
        for q,i in enumerate(ans):
            count = 0
            for j in i:
                if j <= distanceThreshold:count += 1
            if count <= m :res = q;m = count
        return res

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        from collections import defaultdict
        graph = defaultdict(list)
        for start, finish, distance in edges:
            graph[start].append([distance, finish])
            graph[finish].append([distance, start])
        
        #start from each node
        #record all the neighbors that are within the threashold distance from the starting node
        reachable_within_threashold = {}
        import heapq
        
        for house in range(n):
            if house not in graph:
                continue
                #reachable_within_threashold[house] = []
            else:
                heap = [[0, house]]
                reachable_from_this_house = []
                while heap:
                    distance_sofar, cur_house = heapq.heappop(heap)
                    if distance_sofar > distanceThreshold:
                        continue
                    if cur_house in reachable_from_this_house:
                        continue
                    if cur_house in graph:
                        for dis, neighbor in graph[cur_house]:
                            if neighbor not in reachable_from_this_house:
                                heapq.heappush(heap, [dis+distance_sofar,neighbor])
                    if cur_house != house:
                        reachable_from_this_house.append(cur_house)
            reachable_within_threashold[house] = reachable_from_this_house
        
        #print(reachable_within_threashold)
        for house in range(n-1, -1, -1):
            if house not in reachable_within_threashold:
                return house
        
        min_ = float('inf')
        result = float('inf')
        for house in range(n-1, -1, -1):
            cur_no = len(reachable_within_threashold[house])
            if cur_no < min_:
                min_ = cur_no
                result = house
        return result


class Solution:
    def findTheCity(self, n, edges, threshold):
        adj=[[] for _ in range(n)]
        for u,v,w in edges:
            adj[u].append((w,v))
            adj[v].append((w,u))

        ans=0
        mn=100
        for x in range(n):
            cur=0
            vis={x}
            dist=[threshold]*n
            hp=[(0,x)]
            while hp:
                d,u=heappop(hp)
                for w,v in adj[u]:
                    if d+w<=dist[v]:
                        dist[v]=d+w
                        vis.add(v)
                        heappush(hp,(d+w,v))
            if len(vis)<=mn:
                mn=len(vis)
                ans=x
        
        return ans

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
        dist = [[float('inf')] * n for _ in range(n)]
        for i in range(n):
            dist[i][i] = 0
        for pair in edges:
            a, b, c = pair
            dist[a][b] = dist[b][a] = c
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
                        
        res = {len([x for x in dist[i] if x <= distanceThreshold]) : i for i in range(n)}        
        return res[min(res)]

from collections import defaultdict
from collections import deque

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        n2n = defaultdict(list)
        for x, y, w in edges:
            n2n[x].append([y, w])
            n2n[y].append([x, w])

        minds = [[-1] * n for _ in range(n)]

        for i in range(n):
            minds[i][i] = 0

        for x, y, d in edges:
            minds[x][y] = d
            minds[y][x] = d

        for source in range(n):
            visited = [0] * n
            q = deque()
            q.append(source)
            visited[source] = 1

            while q:
                node = q.popleft()
                for next_node, d in n2n.get(node, []):
                    if not visited[next_node]:
                        q.append(next_node)
                        visited[next_node] = 1
                        if minds[source][next_node] == -1 or minds[source][next_node] > minds[source][node] + d:
                            minds[source][next_node] = minds[source][node] + d
                    else:
                        if minds[source][next_node] == -1 or minds[source][next_node] > minds[source][node] + d:
                            minds[source][next_node] = minds[source][node] + d
                            q.append(next_node)


        min_reach = n
        max_node = 0
        for source in range(n):
            reach_count = 0
            for mind in minds[source]:
                if mind != -1 and  mind <= distanceThreshold:
                    reach_count += 1
            if reach_count <= min_reach:
                max_node = source
                min_reach = reach_count

        return max_node


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
        from heapq import heappush, heappop
        
        dis = [[float('inf')]*n for _ in range(n)]
        nei = collections.defaultdict(list)
        for i,j,x in edges:
            dis[i][j] = dis[j][i] = x
            nei[i].append(j)
            nei[j].append(i)
        for i in range(n):
            dis[i][i] = 0
        
        # Dijkstra
        visited = set()
        for i in range(n):
            pool = [(0,i)]                                          # pool[j] = x:  d(i,j) = x    
            while pool:
                x,j = heappop(pool)                                 # x = d(i,j)
                if (i,j) not in visited and x <= distanceThreshold: # early stop, if distance exceeds threshold
                    visited.add((i,j))
                    for k in nei[j]:
                        dis[i][k] = min(dis[i][k], dis[i][j]+dis[j][k])     # dis(i,k) = min(dis(i,k), dis(i,j)+dis(j,k))
                        heappush(pool, (dis[i][k], k))
        globalMin = [-1, -1]
        for i in range(n):
            total = 0
            for j in range(n):
                if dis[i][j] <= distanceThreshold:
                    total += 1
            if globalMin[0] == -1 or total <= globalMin[0]:
                globalMin[0] = total
                globalMin[1] = i
        return globalMin[1]


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        graph = [[float('inf')] * n for i in range(n)]
        for u, v, w in edges:
            graph[u][v] = graph[v][u] = w
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if i == j: graph[i][j] = 0
                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
        minCount, city = float('inf'), -1
        for i in range(n):
            count = sum([1 for j in range(n) if j != i and graph[i][j] <= distanceThreshold])
            if count <= minCount:
                minCount, city = count, i
        return city

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], T: int) -> int:
        dis = collections.defaultdict(lambda: float(\"inf\"))
        for i in range(n):
            dis[i, i] = 0
        for i, j, w in edges:
            dis[i, j] = dis[j, i] = w
            
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dis[i, j] = min(dis[i, j], dis[i, k]+dis[k, j])
        count = [0]*n
        for i in range(n):
            for j in range(n):
                if i == j: continue
                count[i] += dis[i, j] <= T
        mincount = min(count)
        return max(i for i, c in enumerate(count) if c == mincount)
        

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        INF = float('inf')
        AdjMat = [[INF] * n for _ in range(n)]
        
        for i in range(n):
            AdjMat[i][i] = 0
            
        for u,v,w in edges:
            AdjMat[u][v] = w
            AdjMat[v][u] = w
            
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    AdjMat[i][j] = min(AdjMat[i][j], AdjMat[i][k] + AdjMat[k][j])
                    
        d = {}
        for i in range(n):
            c = -1
            for j in range(n):
                if AdjMat[i][j] <= distanceThreshold:
                    c += 1
                    
            d[i] = c
            
        m = min(d.values())
        res = 0
        for k in d:
            if d[k] == m:
                res = max(res,k)
                
        return res


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        from heapq import heappush, heappop
        
        dis = [[float('inf')]*n for _ in range(n)]
        nei = collections.defaultdict(list)
        for i,j,x in edges:
            dis[i][j] = dis[j][i] = x
            nei[i].append(j)
            nei[j].append(i)
        for i in range(n):
            dis[i][i] = 0
        
        # Dijkstra
        visited = set()
        for i in range(n):
            pool = [(0,i)]                                          # pool[j] = x:  d(i,j) = x    
            while pool:
                x,j = heappop(pool)                                 # x = d(i,j)
                if (i,j) not in visited and x <= distanceThreshold: # early stop, if distance exceeds threshold
                    visited.add((i,j))
                    for k in nei[j]:
                        dis[i][k] = min(dis[i][k], x+dis[j][k])     # dis(i,k) = min(dis(i,k), dis(i,j)+dis(j,k))
                        heappush(pool, (dis[i][k], k))

        cities = {sum(d <= distanceThreshold for d in dis[i]):i for i in range(n)}
        return cities[min(cities)]

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        g = [n * [float(\"inf\")] for _ in range(n)]
        
        for a, b, w in edges:
            g[a][b] = g[b][a] = w
            
        # Floyd-Warshall complexity: O(n**3) 
        
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    g[i][j] = min(g[i][j], g[i][k] + g[k][j])
        
        res = -1
        resum = float(\"inf\")
        
        for i in range(n):
            
            isum = 0
            for j in range(n):
                if j != i and g[i][j] <= distanceThreshold:
                    isum += 1
            
            if isum <= resum:
                resum = isum
                res = i
        
        return res



class Solution:
    def findTheCity(self, n, edges, threshold):
        adj = [[] for _ in range(n)]
        for u, v, w in edges:
            adj[u].append((w, v))
            adj[v].append((w, u))

        ans = mn = 100
        for x in range(n):
            cur = 1
            vis = {x}
            dist = [threshold+1] * n
            hp = [(0, x)]
            
            while hp:
                d, u = heappop(hp)
                if d > dist[u]:
                    continue
                for w, v in adj[u]:
                    if d+w < dist[v]:
                        vis.add(v)
                        dist[v] = d+w
                        heappush(hp, (d+w, v))
                        
            if len(vis) <= mn:
                mn = len(vis)
                ans = x
        
        return ans




from heapq import *
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:

        def find_n_neighbours(source_city):

            visited = set()
            heap = [(0, source_city)]

            while heap:
                travelled_distance, curr_city = heappop(heap)
                if curr_city in visited:
                    continue

                if curr_city != source_city:
                    visited.add(curr_city)

                for neigh, distance in graph[curr_city]:
                    if neigh in visited:
                        continue

                    if travelled_distance + distance <= distanceThreshold:
                        heappush(heap, (travelled_distance + distance, neigh))

            return len(visited)

        graph = defaultdict(list)        
        for from_, to, distance in edges:
            graph[from_].append((to, distance))
            graph[to].append((from_, distance))

        neighbours = [find_n_neighbours(i) for i in range(n) ]
        min_count = min(neighbours)
        sel_cities = [i for i in range(n) if neighbours[i] == min_count]
        return sel_cities[-1]


class Solution:
    
    def bfs(self, graph, src, num_nodes, threshold):
        
        d = [float('inf')] * num_nodes
        q = []
        
        q.append(src)
        d[src] = 0
        
        while len(q) > 0:
            u = q.pop(0)
            #print('Exploring edges of u = ', u)
            for v in graph[u]:
                #print(v)
                if d[v[0]] > d[u] + v[1]:
                    d[v[0]] = d[u] + v[1]
                    q.append(v[0])
        #print(d)
        return len([i for i,x in enumerate(d) if x <= threshold and x != 0])
                    
                
        
        
    
    
    
    
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
        # form a graph
        
        graph = collections.defaultdict(list)
        
        for e in edges:
            graph[e[0]].append([e[1], e[2]])
            graph[e[1]].append([e[0], e[2]])
        
        #print(self.bfs(graph, 4, n, distanceThreshold))
        
        min_val = float('inf')
        node = -1
        for i in range(n):
            r = self.bfs(graph, i, n, distanceThreshold)
            if r <= min_val:
                node = i
                min_val = r
                
        return node
                
            
        
        
        


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
    
        # make graph
        dist = [[float('inf')] * n for _ in range(n)]
        
        for u, v, w in edges:
            dist[u][v] = w
            dist[v][u] = w
            
        # use Floyd-Warshall Algorithm to find the minimum dist between any pair of nodes
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    # in case there is a cycle, keep dist[i][j] as inf
                    if i == j:
                        continue
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
        # for all starting node, find their neihboring cities and return the one having fewest neighbors
        mn = n + 1
        output = None
        for start in range(n):
            count = len([d for d in dist[start] if d <= distanceThreshold])
            if count <= mn:
                mn = count
                output = start
        return output

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        oe = {}
        for l, r, w in edges:       
            if l not in oe:
                oe[l] = set()
            if r not in oe:
                oe[r] = set()
            oe[l].add((r, w))
            oe[r].add((l, w))
        
        def dks(been, c, t):
            cw = been[c]        # Current Weight
            if c not in oe:     # No route to any other city
                return
            pending = set()
            for other, weight in oe[c]:
                ow = weight + cw     # From current city to the other city weight
                if ow > distanceThreshold:
                    continue
                
                if other not in been:
                    been[other] = ow
                    pending.add(other)
                    continue
                if been[other] > ow: # Through this city is more effcient
                    been[other] = ow
                    pending.add(other)

            for o in pending:
                dks(been, o, t)
    
            
        smallest = 0
        mc = n+1
        for city in range(n):
            dv = {city: 0}
            dks(dv, city, distanceThreshold)
            # print(dv)
            cities = len(list(dv.keys())) - 1
            if cities <= mc:
                smallest = city
                mc = cities
        return smallest
        


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        adj = collections.defaultdict(dict)
        for a,b,c in edges:
            adj[a][b] = adj[b][a] = c
        def bfs(s, distanceThreshold):
            visited = [False] * n
            dist = [float('inf')] * n
            frontier = [(0, s)]
            
            while frontier:
                d, s = heapq.heappop(frontier)
                if d > distanceThreshold: break
                dist[s] = d
                visited[s] = True
                for t in adj[s]:
                    if not visited[t]:
                        heapq.heappush(frontier, (d + adj[s][t], t))
            return len([d for d in dist if d <= distanceThreshold])
        res = 0
        count = n
        for i in range(n):
            c = bfs(i, distanceThreshold)
            if c <= count:
                res = max(res, i)
                count = c
        return res


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        adj = collections.defaultdict(dict)
        for a,b,c in edges:
            adj[a][b] = adj[b][a] = c
        def bfs(s, distanceThreshold):
            visited = [False] * n
            dist = [float('inf')] * n
            frontier = [(0, s)]
            visited[s] = True
            dist[s] = 0
            while frontier:
                d, s = heapq.heappop(frontier)
                if d > distanceThreshold: break
                dist[s] = d
                visited[s] = True
                for t in adj[s]:
                    if not visited[t]:
                        heapq.heappush(frontier, (d + adj[s][t], t))
            return len([d for d in dist if d <= distanceThreshold])
        res = 0
        count = n
        for i in range(n):
            c = bfs(i, distanceThreshold)
            if c <= count:
                res = max(res, i)
                count = c
        return res


import numpy as np
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        dist=np.inf*np.ones((n,n))
        for k in range(len(edges)):
            dist[edges[k][0],edges[k][1]]=edges[k][2]
            dist[edges[k][1],edges[k][0]]=edges[k][2]
        for k in range(n):
            dist[k,k]=0
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if dist[i,j]>dist[i,k]+dist[j,k]:
                        dist[i,j]=dist[i,k]+dist[j,k]
   
        dist[dist>distanceThreshold]=0
        dist[dist>0]=1

        number=np.sum(dist,1)
     
        curr_min=n
        index=0
        for k in range(n):
            if number[k]<=curr_min:
                curr_min=number[k]
                index=k
        
        return index
        


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:

        matrix = [[float('inf') for x in range(n)] for y in range(n)]
        
        # populate self loops
        for i in range(n):
            matrix[i][i] = 0
        
        # populate initial matrix
        for u,v,w in edges:
            matrix[u][v] = w
            matrix[v][u] = w

        # floyd-warshall       
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    matrix[i][j] = min(matrix[i][j], matrix[i][k]+matrix[k][j])                  
        
        # get amount of below threshold cities
        res = defaultdict(int)
        for i, row in enumerate(matrix):
            for j, dist in enumerate(row):
                if dist <= distanceThreshold and i != j :
                    res[i] += 1
        
        # check if unconnected cities
        unconnected = []
        i = 0
        while i < n:
            if res[i] == 0:
                # not conencted
                unconnected.append(i)
            i += 1
                
        if len(unconnected) == 1:
            return unconnected[0]
        elif len(unconnected) > 1:
            return max(unconnected)
            
        # all cities are connected with each other, get min value
        ans = min(res.values())
        max_city = 0
        
        # if multiple cities with same minimum neighbours, select biggest one
        for city in range(len(res)):
            if res[city] <= ans and city > max_city:
                max_city = city
                

        return max_city

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        #Floyd-Warshall
        
        dis = [[float(\"inf\") for _ in range(n)] for _ in range(n)]
        
        for edge in edges:
            dis[edge[0]][edge[1]] = dis[edge[1]][edge[0]] = edge[2]
        
        # note the outer loop index must be k
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j])
                    
        min_reach = float('inf')
        ans = n
        for i in range(n):
            reach = 0
            for j in range(n):
                if i != j and dis[i][j] <= distanceThreshold:
                    reach += 1
            
            if reach <= min_reach:
                ans = i
                min_reach = reach
 
        return ans

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        g = collections.defaultdict(dict)
        for i, j, w in edges:
            g[i][j] = w
            g[j][i] = w
        t = distanceThreshold
        def dist(u):
            q = [(0, u)]
            ret = {}
            while q:
                d, v = heapq.heappop(q)
                if v in ret:
                    continue
                ret[v] = d
                for k in g[v]:
                    if k not in ret and d + g[v][k] <= t:
                        heapq.heappush(q, (d + g[v][k], k))
            return len(ret)
        ans = None
        num = n + 1
        for i in range(n):
            c = dist(i)
            if c <= num:
                num = c
                ans = i
        return ans
                
            


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        table = [[float('inf') for j in range(n)] for i in range(n)]
        for i in range(n):
            table[i][i] = 0
            
        for v, u, w in edges:
            table[u][v] = w
            table[v][u] = w
            
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    table[i][j] = min(table[i][j], table[i][k] + table[k][j])
                    
        count = [0] * n
        for i in range(n):
            for j in range(n):
                if table[i][j] <= distanceThreshold:
                    count[i] += 1
        
        #print(count)
        #print(table)
        m = min(count)                
        res = -1
        for i in range(n):
            if count[i] == m:
                res = i
                
        return res

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        graph = collections.defaultdict(dict)
        for u, v, w in edges:
            graph[u][v] = w
            graph[v][u] = w

        def dijstra(start, distanceThreshold):
            heap = [(0, start)]
            des = []
            while heap:
                w, u = heapq.heappop(heap)
                if u not in d:
                    d[u] = w
                    for v in graph[u]:
                        if graph[u][v]+ d[u] <= distanceThreshold:
                            heapq.heappush(heap, (graph[u][v]+ d[u], v))
                            if v not in des and v != start:
                                des.append(v)
            return len(des)

        res, count  = 0 , n            
        for i in range(n):
            d = {} 
            des = dijstra(i, distanceThreshold)
            if des <= count:
                res = max(res, i)
                count = des
        return res

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        graph = collections.defaultdict(list)
        for u, v, w in edges: 
            graph[u].append((v, w))
            graph[v].append((u, w))
            
        for k in graph: 
            graph[k].sort(key = lambda x: x[1])
        
            
        def dijk(i, budget): 
            seen, pq = set(), [(0, i, 0)]
            while pq: 
                cost, u, steps = heapq.heappop(pq)
                seen.add(u)
                for nei, weight in graph[u]: 
                    if nei in seen or cost + weight > budget: 
                        continue
                    else:
                        heapq.heappush(pq, (cost + weight, nei, steps + 1))
                       
                    
            return len(seen)
            
        min_city, ans = n, None
        for i in range(n): 
            n_reachable = dijk(i, distanceThreshold)
            if n_reachable <= min_city: 
                min_city, ans = n_reachable, i
        return ans
            
    # def findTheCity(self, n, edges, maxd):
    #     dis = [[float('inf')] * n for _ in range(n)]
    #     for i, j, w in edges:
    #         dis[i][j] = dis[j][i] = w
    #     for i in range(n):
    #         dis[i][i] = 0
    #     for k in range(n):
    #         for i in range(n):
    #             for j in range(n):
    #                 dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
    #     res = {sum(d <= maxd for d in dis[i]): i for i in range(n)}
    #     return res[min(res)]


class Solution:
    def findTheCity(self, n, edges, maxd):
        dis = [[float('inf')] * n for _ in range(n)]
        for i, j, w in edges:
            dis[i][j] = dis[j][i] = w
        for i in range(n):
            dis[i][i] = 0
            
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
                    
        temp = [sum(d <= maxd for d in dis[i]) for i in range(n)]
        return [i for i, x in enumerate(temp) if x == min(temp)][-1]


import heapq
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
            def djikstras(edges, cities, src):
                matrix = {}
                for edge in edges:
                    if edge[0] not in matrix:
                        matrix[edge[0]] = []
                    matrix[edge[0]].append((edge[1], edge[2]))
                    #This line holds good only if the graph is bidirectional
                    if edge[1] not in matrix:
                        matrix[edge[1]] = []
                    matrix[edge[1]].append((edge[0], edge[2]))

                vertices = []
                visited = []
                heapq.heappush(vertices, (0, src))
                while vertices :
                    vertexDist, vertex = heapq.heappop(vertices)
                    if vertex in visited:
                        continue
                    visited.append(vertex)
                    if vertexDist <= distanceThreshold:
                        cities.append(vertex)
                        if vertex in matrix:
                            for (v, w) in matrix[vertex]:
                                newDist = vertexDist + w
                                heapq.heappush(vertices, (newDist , v))
                return cities
            
            cityList = []
            finalCityList = []
            for i in range(n):
                cities = djikstras(edges, [], i)
                #print(cities, i)
                #Removing source city
                if cities:
                    heapq.heappush(cityList, (len(cities), i*-1))
                #print(cityList)
            
            return heapq.heappop(cityList)[1]*-1

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        g = collections.defaultdict(list)
        for f, t, w in edges:
            g[f].append((t, w))
            g[t].append((f, w))
        
        def bfs(i):
            q = [(0, i)]
            visited = {i}
            while q:
                w, j = heapq.heappop(q)
                visited.add(j)
                for k, w_ in g[j]:
                    if k not in visited and w + w_ <= distanceThreshold:
                        heapq.heappush(q, (w + w_, k))
            return visited
        
        return -min([(len(bfs(i)), -i) for i in range(n)])[1]

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        graph = collections.defaultdict(list)
        for u, v, w in edges: 
            graph[u].append((v, w))
            graph[v].append((u, w))
            
        # for k in graph: 
        #     graph[k].sort(key = lambda x: x[1])
        
            
        def dijk(i, budget): 
            seen, pq = set(), [(0, i, 0)]
            while pq: 
                cost, u, steps = heapq.heappop(pq)
                seen.add(u)
                for nei, weight in graph[u]: 
                    if nei in seen or cost + weight > budget: 
                        continue
                    else:
                        heapq.heappush(pq, (cost + weight, nei, steps + 1))
                       
                    
            return len(seen)
            
        min_city, ans = n, None
        for i in range(n): 
            n_reachable = dijk(i, distanceThreshold)
            if n_reachable <= min_city: 
                min_city, ans = n_reachable, i
        return ans
            
    # def findTheCity(self, n, edges, maxd):
    #     dis = [[float('inf')] * n for _ in range(n)]
    #     for i, j, w in edges:
    #         dis[i][j] = dis[j][i] = w
    #     for i in range(n):
    #         dis[i][i] = 0
    #     for k in range(n):
    #         for i in range(n):
    #             for j in range(n):
    #                 dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
    #     res = {sum(d <= maxd for d in dis[i]): i for i in range(n)}
    #     return res[min(res)]


from collections import defaultdict
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        graph = [[math.inf for _ in range(n)] for _ in range(n)]
        for source, sink, cost in edges:
            graph[source][sink] = cost
            graph[sink][source] = cost
        for k in range(n):
            for i in range(n):
                if i == k: continue
                for j in range(n):
                    if i == j or j == k: continue
                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
        counts_map = defaultdict(lambda: -1)
        for i in range(n):
            count = len([x for x in graph[i] if x <= distanceThreshold])
            counts_map[count] = max(counts_map[count], i)
        return counts_map[min(counts_map.keys())]


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        # Floyd Washall
        # dp[i][j] 表示 uv 之间的最小距离
        dp = [ n * [float('inf')] for _ in range(n)]
        
        for f, t, w in edges:
            dp[f][t] = dp[t][f] = w
            
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dp[i][j] = min(dp[i][k] + dp[k][j], dp[i][j])
                    
        res = -1
        minv = float('inf')
        for i in range(n):
            count = 0
            for j in range(n):
                if i != j and dp[i][j] <= distanceThreshold:
                    count += 1
            if count <= minv:
                minv = count
                res = i
        return res
        
        

                    
                    
            
                    
            
            


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        g = collections.defaultdict(list)
        
        for i , j , w in edges:
            g[i].append((j,w))
            g[j].append((i,w))
            
        def neighbours(i):    
            heap = [(0,i)]
            d = {} # keeps the track of visited array 

            while heap:
                distance , node = heappop(heap)
                if node in d:  # adding to the visited array 
                    continue
                if node != i:
                    d[node] = distance

                for nei,w in g[node]:
                    if nei in d:
                        continue
                    if distance+w <= distanceThreshold:
                        heappush(heap,(distance+w,nei))
            return len(d)
                
        
        return max([(neighbours(city), city) for city in range(n)], key=lambda x: (-x[0], x[1]))[-1]


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        graph = collections.defaultdict(set)
        for u, v, w in edges: 
            graph[u].add((v, w))
            graph[v].add((u, w))
            
        def dijk(i, budget): 
            seen, pq = set(), [(0, i, 0)]
            while pq: 
                cost, u, steps = heapq.heappop(pq)
                seen.add(u)
                for nei, weight in graph[u]: 
                    if nei in seen or cost + weight > budget: 
                        continue
                    heapq.heappush(pq, (cost + weight, nei, steps + 1))
            return len(seen)
            
        min_city, ans = n, None
        for i in range(n): 
            n_reachable = dijk(i, distanceThreshold)
            if n_reachable <= min_city: 
                min_city, ans = n_reachable, i
        return ans
            


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        graph = collections.defaultdict(set)
        for u, v, w in edges: 
            graph[u].add((v, w))
            graph[v].add((u, w))
            
        def dijk(i, budget): 
            seen, pq = set(), [(0, i, 0)]
            while pq: 
                cost, u, steps = heapq.heappop(pq)
                seen.add(u)
                for nei, weight in graph[u]: 
                    if nei in seen or cost + weight > budget: 
                        continue
                    heapq.heappush(pq, (cost + weight, nei, steps + 1))
            return len(seen)
            
        min_city, ans = n, None
        for i in range(n): 
            n_reachable = dijk(i, distanceThreshold)
            if n_reachable <= min_city: 
                min_city, ans = n_reachable, i
        return ans
            
    # def findTheCity(self, n, edges, maxd):
    #     dis = [[float('inf')] * n for _ in range(n)]
    #     for i, j, w in edges:
    #         dis[i][j] = dis[j][i] = w
    #     for i in range(n):
    #         dis[i][i] = 0
    #     for k in range(n):
    #         for i in range(n):
    #             for j in range(n):
    #                 dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
    #     res = {sum(d <= maxd for d in dis[i]): i for i in range(n)}
    #     return res[min(res)]


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        weight = collections.defaultdict(dict)
        for u, v, w in edges:
            weight[u][v] = w
            weight[v][u] = w
        
        def getNumberOfNeighbors(city):
            heap = [(0, city)]
            dist = {}
            
            while heap:
                w, u = heapq.heappop(heap)
                if u not in dist and u != city:
                    dist[u] = w
                for v in weight[u]:
                    if v in dist:
                        continue
                    if w + weight[u][v] <= distanceThreshold:
                        heapq.heappush(heap, (w+weight[u][v], v))
            return len(dist)
        minCount = float('inf')
        ans = None
        for i in range(n):
            count = getNumberOfNeighbors(i)
            if count <= minCount:
                ans = i
                minCount = count
        return ans
        


import numpy as np
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        A = np.zeros([n, n])    
        for e in edges:
            A[e[0]][e[1]] = e[2]
            A[e[1]][e[0]] = e[2]
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                if A[i][j] == 0:
                    A[i][j] = np.inf
        for k in range(n):
            for i in range(n):
                if (i == k):
                    continue 
                for j in range(n):
                    if (j == k):
                        continue
                    A[i, j] = min(A[i, j], A[i, k] + A[k, j])
        #print(A)
        count = np.sum(A <= distanceThreshold, axis=0)
        minn = count[0]
        #print(count)
        argminn = 0
        for i, c in enumerate(count):
            if c <= minn:
                minn = c
                argminn = i
        return argminn


import sys
class Solution:
    
    def constructGraph(self, edges, n):
        graph = [[sys.maxsize for i in range(n)] for j in range(n)]
        for i, j, k in edges:
            graph[i][j] = k
            graph[j][i] = k
        return graph
    
    def floydWarshall(self, graph, n):
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if i == j:
                        graph[i][j] = 0
                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
                    graph[j][i] = graph[i][j]
    
    def getCitiesUnderThreshold(self, graph, distanceThreshold, n):
        arr = [None for i in range(n)]
        for i in range(n):
            lis = []
            for j in range(n):
                if graph[i][j] <= distanceThreshold and graph[i][j] != 0:
                    lis.append(j)
            arr[i] = lis
        return arr
    
    def cityWithLeastNumber(self, arr):
        minNum = sys.maxsize
        for i, j in enumerate(arr):
            if len(j) <= minNum:
                minNum = len(j)
                curr = i
        return curr
    
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        graph = self.constructGraph(edges, n)
        self.floydWarshall(graph, n)
        arr = self.getCitiesUnderThreshold(graph, distanceThreshold, n)
        curr = self.cityWithLeastNumber(arr)
        return curr

import heapq
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
            def djikstras(matrix, cities, src):
                vertices = []
                visited = []
                heapq.heappush(vertices, (0, src))
                while vertices :
                    vertexDist, vertex = heapq.heappop(vertices)
                    if vertex in visited:
                        continue
                    visited.append(vertex)
                    if vertexDist <= distanceThreshold:
                        cities.append(vertex)
                        if vertex in matrix:
                            for (v, w) in matrix[vertex]:
                                newDist = vertexDist + w
                                heapq.heappush(vertices, (newDist , v))
                return cities
            
            matrix = {}
            for edge in edges:
                if edge[0] not in matrix:
                    matrix[edge[0]] = []
                matrix[edge[0]].append((edge[1], edge[2]))
                #This line holds good only if the graph is bidirectional
                if edge[1] not in matrix:
                    matrix[edge[1]] = []
                matrix[edge[1]].append((edge[0], edge[2]))
            cityList = []
            for i in range(n):
                cities = []
                if i in matrix:
                    cities = djikstras(matrix, [], i)
                else:
                    cities.append(i)
                heapq.heappush(cityList, (len(cities), i*-1))
            #print(cityList)
            return heapq.heappop(cityList)[1]*-1

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
        
        
        city=0
        value=float(\"inf\")
        graph=defaultdict(list)
        for i,j,c in edges:
            graph[i].append([j,c])
            graph[j].append([i,c])
        
        def heap(start):
            visited=set()
            minheap=[(0,start)]
            while minheap:
                cost,node=heapq.heappop(minheap)
                if cost<=distanceThreshold:
                    visited.add(node)
                else:
                    continue
                for i,j in graph[node]:
                    if i not in visited:
                        heapq.heappush(minheap,(j+cost,i))
            return len(visited)-1
        for i in range(n):
            ans=heap(i)
            if ans<=value:
                value=ans
                city=i
        return city
        

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        L = [[[float('inf') for i in range(n+1)] for j in range(n)] for k in range(n)]

        for u,v,w in edges:
            L[u][v][0] = w
            L[v][u][0] = w
        

        for k in range(1,n+1):
            for i in range(n):
                for j in range(n):
                    if(j==i):
                        continue
                    L[i][j][k] = min(L[i][j][k-1], L[i][k-1][k-1]+L[k-1][j][k-1])

        min_ct = float('inf')
        minval = n-1

        for i in range(n-1,-1,-1):
            ct = 0
            for j in range(n):
                if(i==j):
                    continue
                if(L[i][j][n]<=distanceThreshold):
                    ct += 1
            if(ct<min_ct):
                min_ct = ct
                minval = i
        return minval


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        map = collections.defaultdict(set)
        for f, t, w in edges:
            map[f].add((t, w))
            map[t].add((f, w))
        stack = []
        empty = -float(\"inf\")
        res = 0
        seen = []
        for i in range(n):
            seen.append(collections.defaultdict(int))
            stack.append((i, i, 0))
            if i not in map:
                empty = i
        if empty != -float(\"inf\"):
            return empty
        while stack:
            f, t, w = stack.pop()
            for a, b in map[t]:
                if a not in seen[f] and w + b <= distanceThreshold and a != f:
                    seen[f][a] = w + b
                    stack.append((f, a, w + b))
                elif a in seen[f] and w + b <= seen[f][a] and a != f:
                    seen[f][a] = w + b
                    stack.append((f, a, w + b))
        l = float(\"inf\")
        for k in range(len(seen)):
            if len(seen[k]) <= l:
                l = len(seen[k])
                res = k
        return res

import heapq
from collections import defaultdict
class Solution:
    def findTheCity(self, n: int, edges, distanceThreshold: int) -> int:
        matrix = [[float('inf')]*n for _ in range(n)]
        graph = defaultdict(list)
        for s, e, d in edges:
            matrix[s][e] = d
            matrix[e][s] = d
            graph[s].append(e)
            graph[e].append(s)
        # print(graph)
        # print(matrix)

        def dijkstra(source):
            dist = [float('inf')]*n
            dist[source] = 0
            pq = [(0, source)]
            heapq.heapify(pq)
            while pq:
                # print(pq)
                d, node = heapq.heappop(pq)
                if d > dist[node]:
                    continue
                for next_node in graph[node]:
                    tmp = d + matrix[node][next_node]
                    if tmp < dist[next_node]:
                        dist[next_node] = tmp
                        heapq.heappush(pq, (tmp, next_node))
            # print(source, dist)
            return sum(d <= distanceThreshold for d in dist) - 1

        res, counts = 0, n
        for i in range(n):
            tmp = dijkstra(i)
            # print(tmp, i)
            if tmp <= counts:
                counts = tmp
                res = i
        return res


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
        import collections
        '''
        graph = collections.defaultdict(list)
        
        for edge in edges:
            graph[edge[0]].append([edge[1]], edge[2])
        
        res = []
        
        for i in range(n):
        '''
        
        
        graph = collections.defaultdict(list)
        
        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, w))
        
        print([(self.getNumberOfNeighbors(city, graph, distanceThreshold), city) for city in range(n)]) # [(2, 0), (3, 1), (3, 2), (2, 3)] -> len(dist), city
        print(max([(self.getNumberOfNeighbors(city, graph, distanceThreshold), city) for city in range(n)])) # (3, 2)
        print(max([(self.getNumberOfNeighbors(city, graph, distanceThreshold), city) for city in range(n)], key=lambda x: (-x[0], x[1]))) # (2, 3)
        
        return max([(self.getNumberOfNeighbors(city, graph, distanceThreshold), city) for city in range(n)], key=lambda x: (-x[0], x[1]))[-1] # least distance dict, but max city number
    
    
    def getNumberOfNeighbors(self, city, graph, distanceThreshold):
        heap = [(0, city)]
        dist = {}

        while heap:
            currW, visitedCity = heapq.heappop(heap)
            if visitedCity in dist:
                continue
            if city != visitedCity:    
                dist[visitedCity] = currW
            for neighborCity, w in graph[visitedCity]:
                if neighborCity in dist:
                    continue
                if currW + w <= distanceThreshold:
                    heapq.heappush(heap, (currW + w, neighborCity))
        return len(dist)

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
        import collections
        '''
        graph = collections.defaultdict(list)
        
        for edge in edges:
            graph[edge[0]].append([edge[1]], edge[2])
        
        res = []
        
        for i in range(n):
        '''
        
        
        graph = collections.defaultdict(list)
        
        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, w))
        
        print([(self.getNumberOfNeighbors(city, graph, distanceThreshold), city) for city in range(n)]) # [(2, 0), (3, 1), (3, 2), (2, 3)] -> len(dist), city
        print(max([(self.getNumberOfNeighbors(city, graph, distanceThreshold), city) for city in range(n)])) # (3, 2)
        print(max([(self.getNumberOfNeighbors(city, graph, distanceThreshold), city) for city in range(n)], key=lambda x: (-x[0], x[1]))) # (2, 3)
        
        return max([(self.getNumberOfNeighbors(city, graph, distanceThreshold), city) for city in range(n)], key=lambda x: (-x[0], x[1]))[-1] # least distance dict, but max city number
    
    
    def getNumberOfNeighbors(self, city, graph, distanceThreshold):
        heap = [(0, city)]
        dist = {}

        while heap:
            currW, u = heapq.heappop(heap)
            if u in dist:
                continue
            if u != city:    
                dist[u] = currW
            for v, w in graph[u]:
                if v in dist:
                    continue
                if currW + w <= distanceThreshold:
                    heapq.heappush(heap, (currW + w, v))
        return len(dist)

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        map = collections.defaultdict(list)
        for f, t, w in edges:
            map[f].append((t, w))
            map[t].append((f, w))
        stack = []
        empty = -float(\"inf\")
        res = 0
        seen = []
        for i in range(n):
            seen.append(collections.defaultdict(int))
            stack.append((i, i, 0))
            if i not in map:
                empty = i
        if empty != -float(\"inf\"):
            return empty
        while stack:
            f, t, w = stack.pop()
            for a, b in map[t]:
                if a not in seen[f] and w + b <= distanceThreshold and a != f:
                    seen[f][a] = w + b
                    stack.append((f, a, w + b))
                elif a in seen[f] and w + b <= seen[f][a] and a != f:
                    seen[f][a] = w + b
                    stack.append((f, a, w + b))
        l = float(\"inf\")
        for k in range(len(seen)):
            if len(seen[k]) <= l:
                l = len(seen[k])
                res = k
        return res

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
        graph = defaultdict(list)
        output = []
        
        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, w))
        
        for i in range(n):
            
            #distance , node
            queue = [(i, 0)]
            curr = {}
            
            while queue:
                node, dist = heapq.heappop(queue)
                
                if node in curr and dist >= curr[node]:
                    continue
                
                curr[node] = dist
                
                for nei, newDist in graph[node]:
                    if newDist + dist <= distanceThreshold:
                        heapq.heappush(queue,(nei, newDist + dist))
            
            output.append(len(curr)-1)
        
        for node in reversed(range(len(output))):
            if output[node] == min(output):
                return node

import heapq
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
            def djikstras(matrix, cities, src):
                vertices = []
                visited = []
                heapq.heappush(vertices, (0, src))
                while vertices :
                    vertexDist, vertex = heapq.heappop(vertices)
                    if vertex in visited:
                        continue
                    visited.append(vertex)
                    if vertexDist <= distanceThreshold:
                        cities.append(vertex)
                        if vertex in matrix:
                            for (v, w) in matrix[vertex]:
                                newDist = vertexDist + w
                                heapq.heappush(vertices, (newDist , v))
                return cities
            
            cityList = []
            finalCityList = []
            matrix = {}
            for edge in edges:
                if edge[0] not in matrix:
                    matrix[edge[0]] = []
                matrix[edge[0]].append((edge[1], edge[2]))
                #This line holds good only if the graph is bidirectional
                if edge[1] not in matrix:
                    matrix[edge[1]] = []
                matrix[edge[1]].append((edge[0], edge[2]))
            for i in range(n):
                cities = djikstras(matrix, [], i)
                #print(cities, i)
                #Removing source city
                if cities:
                    heapq.heappush(cityList, (len(cities), i*-1))
                #print(cityList)
            
            return heapq.heappop(cityList)[1]*-1

class Solution:
    import heapq
    import collections
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:

        min_node = -1
        min_val = float(\"inf\")

        graph = collections.defaultdict(list)
        for s, e, d in edges:
            graph[s].append((e, d))
            graph[e].append((s, d))

        for node in range(n):
            pq = [(0, node)]
            seen = set([node])

            while pq:
                td, name = heapq.heappop(pq)
                seen.add(name)
                for nex, do in graph[name]:
                    if do + td <= distanceThreshold and nex not in seen:
                        heapq.heappush(pq, (do + td, nex))

            count = len(seen)

            if count <= min_val:
                min_node = node
                min_val = count

        return min_node


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        g = {}
        for u, v, w in edges:
            if u in g:
                g[u].append((v, w))
            else:
                g[u] = [(v, w)]
            if v in g:
                g[v].append((u, w))
            else:
                g[v] = [(u, w)]
        def numOfNb(city):
            minheap = [(0, city)]
            dist = {}
            while minheap:
                currw, u = heapq.heappop(minheap)
                if u != city:
                    dist[u] = currw
                if u not in g:
                    continue
                for v, w in g[u]:
                    if v in dist:
                        continue
                    if currw + w <= distanceThreshold:
                        heapq.heappush(minheap, (currw + w, v))
            return len(dist)
        ans = 0
        minnb = n
        for i in range(n):
            nb = numOfNb(i)
            if nb <= minnb:
                minnb = nb
                ans = i
        return ans

class Solution:
    import heapq
    import collections
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:

        min_node = -1
        min_val = float(\"inf\")

        graph = collections.defaultdict(list)
        for s, e, d in edges:
            graph[s].append((e, d))
            graph[e].append((s, d))

        for node in range(n):
            pq = [(0, node)]
            seen = set()
            seen.add(node)

            while pq:
                td, name = heapq.heappop(pq)
                seen.add(name)
                for nex, do in graph[name]:
                    if do + td <= distanceThreshold and nex not in seen:
                        heapq.heappush(pq, (do + td, nex))

            count = len(seen)

            if count <= min_val:
                min_node = node
                min_val = count

        return min_node


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        g = {}
        for u, v, w in edges:
            if u in g:
                g[u].append((v, w))
            else:
                g[u] = [(v, w)]
            if v in g:
                g[v].append((u, w))
            else:
                g[v] = [(u, w)]
        def numOfNb(city):
            minheap = [(0, city)]
            dist = {}
            while minheap:
                currw, u = heapq.heappop(minheap)
                if u != city:
                    dist[u] = currw
                if u not in g or currw > distanceThreshold:
                    continue
                for v, w in g[u]:
                    if v in dist:
                        continue
                    if currw + w <= distanceThreshold:
                        heapq.heappush(minheap, (currw + w, v))
            return len(dist)
        ans = 0
        minnb = n
        for i in range(n):
            nb = numOfNb(i)
            if nb <= minnb:
                minnb = nb
                ans = i
        return ans

from heapq import *
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
        
        g = collections.defaultdict(list)
        
        for i , j , w in edges:
            g[i].append((j,w))
            g[j].append((i,w))
            
        def neighbours(i):    
            
            heap = [(0,i)]
            d = {}

            while heap:

                distance , node = heappop(heap)

                if node in d:
                    continue

                if node != i:
                    d[node] = distance

                for nei,w in g[node]:
                    
                    if nei in d:
                        continue

                    if distance+w <= distanceThreshold:
                        heappush(heap,(distance+w,nei))
                
            return len(d)
                
        
        return max([(neighbours(city), city) for city in range(n)], key=lambda x: (-x[0], x[1]))[-1]

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
                        
        g = collections.defaultdict(list)
        for u, v, w in edges:
            g[u].append((v, w))
            g[v].append((u, w))
            
        def dkstr(n):
            q = [(0, n)]
            visited = set()
            while q:
                dis, node = heapq.heappop(q)
                visited.add(node)
                for adj, w in g[node]:
                    if dis+w <= distanceThreshold and adj not in visited:
                        heapq.heappush(q, (dis+w, adj))
        
            return len(visited) - 1
        
        num_city = float(\"inf\")
        ans = 0
        for i in range(n):
            num_local = dkstr(i)
            if num_local <= num_city:
                num_city = num_local
                ans = i

        return ans
        

class Solution:
\tdef findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
\t\tmap = collections.defaultdict(set)
\t\tfor f, t, w in edges:
\t\t\tmap[f].add((t, w))
\t\t\tmap[t].add((f, w))
\t\tstack = []
\t\tempty = -float(\"inf\")
\t\tres = 0
\t\tseen = []
\t\tfor i in range(n):
\t\t\tseen.append(collections.defaultdict(int))
\t\t\tstack.append((i, i, 0))
\t\t\tif i not in map:
\t\t\t\tempty = i
\t\tif empty != -float(\"inf\"):
\t\t\treturn empty
\t\twhile stack:
\t\t\tf, t, w = stack.pop()
\t\t\tfor a, b in map[t]:
\t\t\t\tif a not in seen[f] and w + b <= distanceThreshold and a != f:
\t\t\t\t\tseen[f][a] = w + b
\t\t\t\t\tstack.append((f, a, w + b))
\t\t\t\telif a in seen[f] and w + b <= seen[f][a] and a != f:
\t\t\t\t\tseen[f][a] = w + b
\t\t\t\t\tstack.append((f, a, w + b))
\t\tl = float(\"inf\")
\t\tfor k in range(len(seen)):
\t\t\tif len(seen[k]) <= l:
\t\t\t\tl = len(seen[k])
\t\t\t\tres = k
\t\treturn res

import heapq
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
            def djikstras(edges, cities, src):
                vertices = []
                visited = []
                heapq.heappush(vertices, (0, src))
                while vertices :
                    vertexDist, vertex = heapq.heappop(vertices)
                    if vertex in visited:
                        continue
                    visited.append(vertex)
                    if vertexDist <= distanceThreshold:
                        cities.append(vertex)
                        if vertex in matrix:
                            for (v, w) in matrix[vertex]:
                                newDist = vertexDist + w
                                heapq.heappush(vertices, (newDist , v))
                return cities
            
            cityList = []
            finalCityList = []
            matrix = {}
            for edge in edges:
                if edge[0] not in matrix:
                    matrix[edge[0]] = []
                matrix[edge[0]].append((edge[1], edge[2]))
                #This line holds good only if the graph is bidirectional
                if edge[1] not in matrix:
                    matrix[edge[1]] = []
                matrix[edge[1]].append((edge[0], edge[2]))
            for i in range(n):
                cities = djikstras(edges, [], i)
                #print(cities, i)
                #Removing source city
                if cities:
                    heapq.heappush(cityList, (len(cities), i*-1))
                #print(cityList)
            
            return heapq.heappop(cityList)[1]*-1

from collections import defaultdict
class Solution:
    
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        dist = defaultdict(list)
        for x, y, w in edges:
            dist[x].append((y, w))
            dist[y].append((x, w))
        
        curmin_idx, curmin_val = None, None 
        def dfs(idx, visited, threshold):
            if threshold < 0: return
            visited[idx] = threshold 
            
            for iidx, weight in dist[idx]:
                if (threshold - weight) > visited[iidx]:
                    dfs(iidx, visited, threshold - weight)
                    
        for i in range(n):
            visited = [-1] * n
            dfs(i, visited, distanceThreshold)
            cur_visited = sum(1 for v in visited if v >= 0)
            if curmin_val is None or cur_visited <= curmin_val:
                curmin_val = cur_visited
                curmin_idx = i
                          
             
        return curmin_idx
        
            


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], d: int) -> int:
        if n==2:
            return 1
        
        graph = {x:[] for x in range(n)}
        for edge in edges:
            graph[edge[0]].append((edge[1],edge[2]))
            graph[edge[1]].append((edge[0],edge[2]))
        
        
        def reachable(node, visited, threshold, dist):
            for nei in graph[node]:
                if dist+nei[1]<visited[nei[0]] and dist+nei[1]<=threshold:
                    visited[nei[0]] = dist+nei[1] 
                    reachable(nei[0], visited, threshold, dist+nei[1])
                    
        res = 0
        temp = n
        for i in reversed(list(range(n))):
            visited = [float('inf') for _ in range(n)]
            visited[i] = 0
            c = 0
            dist = 0
            for nei in graph[i]:
                if dist+nei[1]<visited[nei[0]] and dist+nei[1]<=d:
                    visited[nei[0]] = dist+nei[1] 
                    reachable(nei[0], visited, d,dist+nei[1])
            
            for val in visited:
                if val>0 and val!=float('inf'):
                    c+=1
        
            # print(c,i)
            if c < temp :
                res = i
                temp = c
        return res


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        adj = [[] for i in range(n)]
        res = [0 for i in range(n)]
        ans = float('inf')
        city = -1
        
        # create adj list
        for i in edges:
            a, b, c = i
            adj[a].append((b, c))
            adj[b].append((a, c))        
        
        for i in range(n):
            visited = [float('inf') for j in range(n)]
            visited[i] = 0
            
            traverse(i, visited, distanceThreshold, 0, adj)
            
            res[i] = n - visited.count(float('inf'))  
            
        for i in range(n):
            if res[i] <= ans:
                ans = res[i]
                city = i
            
        return city
    
def traverse(curr, visited, threshold, dist, adj):
    
    if dist > threshold:
        return
    
    visited[curr] = dist
    
    for pair in adj[curr]:
        city, next_dist = pair
        if dist + next_dist <= visited[city]:
            traverse(city, visited, threshold, dist + next_dist, adj)

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], d: int) -> int:
        if n==2:
            return 1
        
        graph = {x:[] for x in range(n)}
        for edge in edges:
            graph[edge[0]].append((edge[1],edge[2]))
            graph[edge[1]].append((edge[0],edge[2]))
        
        
        def reachable(node, visited, threshold, dist):
            for nei in graph[node]:
                if dist+nei[1]<visited[nei[0]] and dist+nei[1]<=threshold:
                    visited[nei[0]] = dist+nei[1] 
                    reachable(nei[0], visited, threshold, dist+nei[1])
                    
        res = 0
        temp = n
        for i in reversed(list(range(n))):
            visited = [float('inf') for _ in range(n)]
            visited[i] = 0
            c = 0
            dist = 0
            for nei in graph[i]:
                if dist+nei[1]<visited[nei[0]] and dist+nei[1]<=d:
                    visited[nei[0]] = dist+nei[1] 
                    reachable(nei[0], visited, d,dist+nei[1])
            
            for val in visited:
                if val>0 and val!=float('inf'):
                    c+=1
        
            print((c,i))
            if c < temp :
                res = i
                temp = c
        return res


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        MAX_VAL = 1e6 + 1
        self.graph = [[MAX_VAL for _ in range(n)] for _ in range(n)]
        for idx in range(n): self.graph[idx][idx] = 0
        for edge in edges:
            self.graph[edge[0]][edge[1]] = edge[2]
            self.graph[edge[1]][edge[0]] = edge[2]
        for k in range(n):
            for i in range(n):
                for j in range(i + 1, n):
                    if self.graph[i][k] + self.graph[k][j] < self.graph[i][j]:
                        self.graph[i][j] = self.graph[i][k] + self.graph[k][j]
                        self.graph[j][i] = self.graph[i][k] + self.graph[k][j]
        results = []
        for idx in range(n):
            results.append((idx, len([_ for _ in range(n) if self.graph[idx][_] <= distanceThreshold])))
        return sorted(results, key=lambda x: (x[1], -x[0]))[0][0]

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
        if n == 0:
            return 0
        
        if len(edges) == 0:
            return 0
        
        dict1 = collections.defaultdict(list)
        dict2 = collections.defaultdict(list)
        for edge in edges:
            dict1[edge[0]].append((edge[1],edge[2]))
            dict1[edge[1]].append((edge[0],edge[2]))
    
        self.dict1 = dict1
        self.distanceThreshold = distanceThreshold
        tempres = []
        for i in range(n):
            temp = self.neighbours(i)
            tempres.append((temp,i))
        print(tempres)
        return sorted(tempres, key = lambda x:([x[0]],[-x[1]]))[0][1] 
    
    def neighbours(self,i):    
            
            heap = [(0,i)]
            d = {}

            while heap:

                distance , node = heappop(heap)

                if node in d:
                    continue

                if node != i:
                    d[node] = distance

                for nei,w in self.dict1[node]:
                    
                    if nei in d:
                        continue

                    if distance+w <= self.distanceThreshold:
                        heappush(heap,(distance+w,nei))
                
            return len(d)
        
        
        
        
        
        
                             
        
            
        
        


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
        import collections
        '''
        graph = collections.defaultdict(list)
        
        for edge in edges:
            graph[edge[0]].append([edge[1]], edge[2])
        
        res = []
        
        for i in range(n):
        '''
        
        
        graph = collections.defaultdict(list)
        
        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, w))
            
        return max([(self.getNumberOfNeighbors(city, graph, distanceThreshold), city) for city in range(n)], key=lambda x: (-x[0], x[1]))[-1]
    
    
    def getNumberOfNeighbors(self, city, graph, distanceThreshold):
        heap = [(0, city)]
        dist = {}

        while heap:
            currW, u = heapq.heappop(heap)
            if u in dist:
                continue
            if u != city:    
                dist[u] = currW
            for v, w in graph[u]:
                if v in dist:
                    continue
                if currW + w <= distanceThreshold:
                    heapq.heappush(heap, (currW + w, v))
        return len(dist)

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        def getNumberOfNeighbors(city, graph):
            heap = [(0, city)]
            dist = {}
            
            while heap:
                currW, u = heapq.heappop(heap)
                if u in dist:
                    continue
                if u != city:    
                    dist[u] = currW
                for v, w in graph[u].items():
                    if v in dist:
                        continue
                    if currW + w <= distanceThreshold:
                        heapq.heappush(heap, (currW + w, v))
            return len(dist)
        
        adjList = collections.defaultdict(dict)
        for start, end, weight in edges:
            adjList[start][end] = weight
            adjList[end][start] = weight
        
        disconnected_cities = set([i for i in range(n)]) - adjList.keys()
        if disconnected_cities:
            return max(disconnected_cities)
        
        min_so_far = float('inf')
        cities = []
        
        for city in adjList.keys():
            count = getNumberOfNeighbors(city, adjList)

            if count < min_so_far:
                min_so_far = count
                cities = [city]
            elif count == min_so_far:
                cities.append(city)
        return max(cities)

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
        graph = collections.defaultdict(list)
        
        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, w))
            
        def getNumberOfNeighbors(city):
            heap = [(0, city)]
            dist = {}
            
            while heap:
                currW, u = heapq.heappop(heap)
                if u in dist:
                    continue
                if u != city:    
                    dist[u] = currW
                for v, w in graph[u]:
                    if v in dist:
                        continue
                    if currW + w <= distanceThreshold:
                        heapq.heappush(heap, (currW + w, v))
            return len(dist)
        
        return max([(getNumberOfNeighbors(city), city) for city in range(n)], key=lambda x: (-x[0], x[1]))[-1]

from collections import defaultdict
from heapq import heapify,heappush,heappop
import math
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
        graph  = defaultdict(list)
        
        for i in range(len(edges)):
            graph[edges[i][0]].append([edges[i][1],edges[i][2]])
            graph[edges[i][1]].append([edges[i][0],edges[i][2]])
            
        res = [0]*n
        
        for i in range(n):
            visited  = [False]*n
            distance = [math.inf]*n
            distance[i]=0
            stack =[[0,i]]
            count = 0
            while(len(stack)!=0):
                p = heappop(stack)
                if p[0]>distanceThreshold:
                    break
                visited[p[1]] = True
                for node in graph[p[1]]:
                    if visited[node[0]]==False:
                        if p[0]+node[1]<distance[node[0]]:
                            distance[node[0]]= distance[p[1]]+node[1]
                            heappush(stack,[distance[node[0]],node[0]])
            count = 0
            for j in range(n):
                if visited[j]==True:
                    count+=1
            res[i]=count-1
        m = math.inf
        pos = 0
        for i in range(n):
            if res[i]<=m:
                m =res[i]
                pos = i
                
        return pos

class Solution:
    def findTheCity(self, n, edges, threshold):
        adj=[[] for _ in range(n)]
        for u,v,w in edges:
            adj[u].append((w,v))
            adj[v].append((w,u))

        ans=0
        min_cities=100
        for x in range(n):
            cur_cities=0
            vis={x}
            dist=[threshold+1]*n
            hp=[(0,x)]
            while hp:
                d,u=heappop(hp)
                for w,v in adj[u]:
                    if d+w<=threshold and d+w<dist[v]:
                        dist[v]=d+w
                        vis.add(v)
                        heappush(hp,(d+w,v))
            if len(vis)<=min_cities:
                min_cities=len(vis)
                ans=x
        
        return ans

from collections import defaultdict
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        '''
        # Notes:
            return the city with the smallest number of cities that are reachable through some path
        # Appraoch:
            Dijkstra
        '''
        # build the graph
        graph = defaultdict(dict)
        for city1, city2, weight in edges:
            graph[city1][city2] = weight
            graph[city2][city1] = weight

        res, res_reachable = None, float('inf')
        for i in range(n):
            visited = set()
            unvisited = set()
            shortest_distance = [float('inf')] * n
            for j in range(n):
                if j == i:
                    visited.add(j)
                    shortest_distance[i] = 0
                else:
                    unvisited.add(j)
            cur = i
            reachable = defaultdict(set)
            while cur != None:
                for neighbor in graph[cur]:
                    if neighbor not in visited:
                        if shortest_distance[cur] + graph[cur][neighbor] <= distanceThreshold:
                            reachable[i].add(neighbor)
                            if shortest_distance[cur] + graph[cur][neighbor] < shortest_distance[neighbor]:
                                shortest_distance[neighbor] = shortest_distance[cur] + graph[cur][neighbor]
           
                cur = None
                for city in unvisited:
                    if shortest_distance[city] != float('inf'):
                        if cur == None:
                            cur = city
                        else:
                            if shortest_distance[city] < shortest_distance[cur]:
                                cur = city
                if cur != None:
                    visited.add(cur)
                    unvisited.remove(cur)

            if len(reachable[i]) <= res_reachable:
                res_reachable = len(reachable[i])
                res = i
                
        return res

class Solution:
    def dijkstra(self, graph, src):
        dist, visited = {}, collections.defaultdict(bool, {src: True})
        for u in graph:
            dist[u] = float('inf')
        dist[src] = 0

        heap = [(0, src)]
        while heap:
            cur, city = heapq.heappop(heap)
            visited[city] = True
            for to, weight in graph[city]:
                if not visited[to] and dist[to] > cur + weight:
                    dist[to] = cur + weight
                    heapq.heappush(heap, (dist[to], to))

        return dist


    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        graph = collections.defaultdict(list)
        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, w))

        neighbors = collections.defaultdict(int)
        for city in graph:
            for c, dist in list(self.dijkstra(graph, src=city).items()):
                if city != c and dist <= distanceThreshold:
                    neighbors[city] += 1

        for i in range(n):
            if neighbors[i]: pass

        answer, min_neighbors = -1, float('inf')
        for city, num in list(neighbors.items()):
            if num < min_neighbors or (num == min_neighbors and city > answer):
                answer = city
                min_neighbors = num

        return answer


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        h=collections.defaultdict(list)
        for i in edges:
            h[i[0]].append((i[1],i[2]))
            h[i[1]].append((i[0],i[2]))
        #print(h)
        c=0
        no=101
        for i in range(n):
            b=set()
            q=[]
            heapq.heappush(q,(0,i,-1))
            while q:
                x=heapq.heappop(q)
                if x[1] in b:
                    continue
                b.add(x[1])
                #print(x,q,b)
                for j in h[x[1]]:
                    if j[1]+x[0]<=distanceThreshold and j[0]!=x[2] and j[0] not in b:
                        heapq.heappush(q,(j[1]+x[0],j[0],x[1]))
            if len(b)-1<=no:
                no=len(b)-1
                c=i
        return c


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        h=collections.defaultdict(list)
        for i in edges:
            h[i[0]].append((i[1],i[2]))
            h[i[1]].append((i[0],i[2]))
        #print(h)
        c=0
        no=101
        for i in range(n):
            b=set()
            q=[]
            heapq.heappush(q,(0,i,-1))
            while q:
                x=heapq.heappop(q)
                if x[1] in b:
                    continue
                b.add(x[1])
                #print(x,q,b)
                for j in h[x[1]]:
                    if j[1]+x[0]<=distanceThreshold and j[0]!=x[2] and j[0] not in b:
                        heapq.heappush(q,(j[1]+x[0],j[0],x[1]))
            if len(b)-1<=no:
                no=len(b)-1
                c=i
                print((len(b)-1))
        return c


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        adj = collections.defaultdict(dict)
        for a,b,c in edges:
            adj[a][b] = adj[b][a] = c
        def bfs(s, distanceThreshold):
            visited = [False] * n
            dist = [float('inf')] * n
            frontier = [(0, s)]
            visited[s] = True
            dist[s] = 0
            while not all(visited) and frontier:
                d, s = heapq.heappop(frontier)
                if d > distanceThreshold: break
                dist[s] = d
                visited[s] = True
                for t in adj[s]:
                    if not visited[t]:
                        heapq.heappush(frontier, (d + adj[s][t], t))
            return len([d for d in dist if d <= distanceThreshold])
        res = 0
        count = n
        for i in range(n):
            c = bfs(i, distanceThreshold)
            if c <= count:
                res = max(res, i)
                count = c
        return res


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        adj = collections.defaultdict(dict)
        for a,b,c in edges:
            adj[a][b] = adj[b][a] = c
        def bfs(s, distanceThreshold):
            visited = [False] * n
            dist = [float('inf')] * n
            frontier = [(0, s)]
            # visited[s] = True
            # dist[s] = 0
            while not all(visited) and frontier:
                d, s = heapq.heappop(frontier)
                if d > distanceThreshold: break
                dist[s] = d
                visited[s] = True
                for t in adj[s]:
                    if not visited[t]:
                        heapq.heappush(frontier, (d + adj[s][t], t))
            return len([d for d in dist if d <= distanceThreshold])
        res = 0
        count = n
        for i in range(n):
            c = bfs(i, distanceThreshold)
            if c <= count:
                res = max(res, i)
                count = c
        return res


from typing import List
from collections import defaultdict
from heapq import heappush, heappop

class Solution:
\tdef findTheCityFloydWarshall(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
\t\tdist = [[float('inf')] * n for _ in range(n)]
\t\tfor u, v, w in edges:
\t\t\tdist[u][v] = dist[v][u] = w # bidirectional edges
\t\tfor i in range(n):
\t\t\tdist[i][i] = 0

\t\t# floyd-warshall
\t\tfor k in range(n):
\t\t\tfor i in range(n):
\t\t\t\tfor j in range(n):
\t\t\t\t\tdist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
\t\t
\t\tres = {sum(v <= distanceThreshold for v in dist[u]): u for u in range(n)}
\t\treturn res[min(res)]
\t
\tdef findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
\t\tgraph = defaultdict(list)
\t\tfor u, v, w in edges:
\t\t\tgraph[u].append((v, w))
\t\t\tgraph[v].append((u, w))

\t\tans = [float('inf'), float('inf')]

\t\tfor i in range(n):
\t\t\tpq = [(0, i)]
\t\t\tdist = [float('inf')] * n
\t\t\tdist[i] = 0
\t\t\tvisit = [False] * n

\t\t\twhile pq:
\t\t\t\tdist_u, u = heappop(pq)
\t\t\t\tvisit[i] = True
\t\t\t
\t\t\t\tfor v, w in graph[u]:
\t\t\t\t\tif not visit[v]:
\t\t\t\t\t\tif dist[v] > dist[u] + w:
\t\t\t\t\t\t\tdist[v] = dist[u] + w
\t\t\t\t\t\t\tif dist[v] <= distanceThreshold:
\t\t\t\t\t\t\t\theappush(pq, (dist[v], v))

\t\t\tcnt = 0
\t\t\tfor d in dist:
\t\t\t\tif d <= distanceThreshold: cnt += 1
\t\t\t
\t\t\tif cnt < ans[0]:
\t\t\t\tans = [cnt, i]
\t\t\telif cnt == ans[0]:
\t\t\t\tif i > ans[1]:
\t\t\t\t\tans = [cnt, i]
\t\t
\t\treturn ans[1]

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        graph = [[float(\"inf\") for _ in range(n)] for _ in range(n)]
        
        for a in edges:
            graph[a[0]][a[1]] = a[2]
            graph[a[1]][a[0]] = a[2]
            
        for i in range(n):
            graph[i][i] = 0
            
            
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if graph[i][j]>graph[i][k]+graph[k][j]:
                        graph[i][j] = graph[i][k]+graph[k][j]
                        
        count = float(\"inf\")
        node = 0
        for i in range(n):
            a = graph[i]
            c = [x for x in a if x<=distanceThreshold]
            if len(c)<=count:
                count = len(c)
                node = i
                
        return node
            
                    
                    
                    
                
        

def init_graph(edges, n): 
    graph = [[] for _ in range(n)]
    for src, dest, weight in edges: 
        graph[src].append((dest, weight))
        graph[dest].append((src, weight))
    return graph

def run_bfs(src, graph, threshold, n): 
    q = [(0, src)]
    distances = [math.inf for i in range(n)]
    distances[src] = 0
    res = 0
    while(q): 
        distance, node = heapq.heappop(q)
        edges = graph[node]
        print(\"Visiting: \" + str(node))
        for nbr_node, weight in edges: 
            updated_distance = distance + weight
            if distances[nbr_node] > updated_distance and updated_distance<=threshold: 
                print(\"Neighbor: \" + str(nbr_node) + \" distance: \" + str(updated_distance))
                if distances[nbr_node] == math.inf: 
                    print(\"Updating for: \" + str(nbr_node))
                    res = res + 1
                distances[nbr_node] = updated_distance
                heapq.heappush(q, (updated_distance, nbr_node))
    print(\"Returning: \" + str(res))
    return res 

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        if n==0 or not edges: 
            return -1
        
        graph = init_graph(edges, n)
        min_nbrs = math.inf
        min_nbrs_city = -1
        for i in range(n): 
            num_nbrs = run_bfs(i, graph, distanceThreshold, n)
            if num_nbrs <= min_nbrs: 
                min_nbrs = num_nbrs
                min_nbrs_city = max(min_nbrs_city, i)
            
        return min_nbrs_city 
    
    
    
        
            

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        dist = [[float('inf')]*n for _ in range(n)]
        next_city = [[None]*n for _ in range(n)]
        
        for edge in edges:
            dist[edge[0]][edge[1]] = edge[2]
            dist[edge[1]][edge[0]] = edge[2]
            next_city[edge[0]][edge[1]] = edge[1]
        
        for city in range(n):
            dist[city][city] = 0
            next_city[city][city] = city
            
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if dist[i][j] > dist[i][k] + dist[k][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
                        next_city[i][j] = next_city[i][k]
        city_sum_under_thresh = [0]*n
        for i in range(n):
            city_sum_under_thresh[i] += len([ distance for index, distance in enumerate(dist[i]) if distance <= distanceThreshold if index!= i])
        return min([ (index, count) for index, count in enumerate(city_sum_under_thresh)], key = lambda x: (x[1], -x[0]))[0]

# 이웃수가 가장 적은 노드 찾기
# 이웃수가 같다면 번호가 가장 큰 노드 반환

# 1. 모든 노드 다익스트라
# 2. 플로이드와샬
# 우선 adj 만들기
# adj에 연결되 있는 부분 값 넣어주기

# if adj[i][j] + adj[j][k] < adj[i][k]
# adj[i][k] = adj[i][j] + adj[j][k]
def floydWarshall(adj, n):
#     처음에 출발지, 도착지, 경유지 순서로 했을 때는 틀림 왜일까?
    for k in range(n): # 경유지
        for i in range(n): # 출발지
            for j in range(n): # 도착지
                stopOver = adj[i][k] + adj[k][j]
                if(stopOver < adj[i][j]):
                    adj[i][j] = stopOver

class Solution:                 
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        INFI = 2 ** 31
        adj = [[INFI for _ in range(n)] for _ in range(n)]                
        answer = 0
        neighbors = []
        for x in range(n):
            adj[x][x] = 0
        
        for edge in edges:
            adj[edge[0]][edge[1]] = edge[2]
            adj[edge[1]][edge[0]] = edge[2]
        floydWarshall(adj, n)        
        # print(adj)
#         이웃 추가
        for node in adj:
            count = 0 # 이웃 수
            for distance in node:
                if distance <= distanceThreshold:
                    count += 1
            neighbors.append(count-1)
        
        # print(neighbors)
        minCount = min(neighbors)
        # print(neighbors)
        for i, neighCount in enumerate(neighbors):
            if(minCount == neighCount):
                answer = i                
                
        return answer

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        # Floyd-Warshall algo
        _c = [float('inf')] * n
        dv = [list(_c) for _ in range(n)]
        for i in range(n):
            dv[i][i] = 0
        for l, r, w in edges:   # Bidirectional
            dv[l][r] = w
            dv[r][l] = w
        
        for k in range(n):
            for r in range(n):
                for c in range(n):
                    tk = dv[r][k] + dv[k][c]    # R->C through K
                    if dv[r][c] > tk:
                        dv[r][c] = tk
        smallest = 0
        mc = n+1
        
        for r in range(n):
            cities = 0
            for c in range(n):
                if dv[r][c] <= distanceThreshold:
                    print(f'{r} -> {c}; {dv[r][c]} <= {distanceThreshold}')
                    cities += 1
            if cities <= mc:
                smallest = r
                mc = cities
        return smallest
                
    
    \"\"\" Dijkstra's method
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        oe = {}
        for l, r, w in edges:       
            if l not in oe:
                oe[l] = set()
            if r not in oe:
                oe[r] = set()
            oe[l].add((r, w))
            oe[r].add((l, w))
        
        def dks(been, c, t):
            cw = been[c]        # Current Weight
            if c not in oe:     # No route to any other city
                return
            pending = set()
            for other, weight in oe[c]:
                ow = weight + cw     # From current city to the other city weight
                if ow > distanceThreshold:
                    continue
                
                if other not in been:
                    been[other] = ow
                    pending.add(other)
                    continue
                if been[other] > ow: # Through this city is more effcient
                    been[other] = ow
                    pending.add(other)

            for o in pending:
                dks(been, o, t)
    
            
        smallest = 0
        mc = n+1
        for city in range(n):
            dv = {city: 0}
            dks(dv, city, distanceThreshold)
            # print(dv)
            cities = len(dv.keys()) - 1
            if cities <= mc:
                smallest = city
                mc = cities
        return smallest
        \"\"\"
        
        

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], dist: int) -> int:
        if n==2:
            return 1
        
        graph = [[float('inf')]*n for _ in range(n)] 
        for s,e,w in edges:
            graph[s][e] = w
            graph[e][s] = w
        
        
        for i in range(n):
            graph[i][i] = 0
        
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if graph[i][j] > (d:= graph[i][k] + graph[k][j]):
                            graph[i][j] = d
        
        nei = {len(list(filter(lambda x: 0 < x <= dist, graph[i]))): i for i in range(n)}
        # print(nei)
        # print(graph)
        return nei[min(nei)]

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        g = collections.defaultdict(list)
        for f, t, w in edges:
            g[f].append((t, w))
            g[t].append((f, w))
        
        def bfs(i):
            q = [(0, i)]
            dist = [distanceThreshold + 1] * n
            visited = {i}
            while q:
                w, j = heapq.heappop(q)
                if w > dist[j]:
                    continue
                visited.add(j)
                for k, w_ in g[j]:
                    d = w + w_
                    if k not in visited and d <= distanceThreshold and d < dist[k]:
                        heapq.heappush(q, (d, k))
                        dist[k] = d
            return len(visited)
        
        return -min([(bfs(i), -i) for i in range(n)])[1]

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        dist = [[float('inf')] * n for _ in range(n)]
        for u, v, w in edges:
            dist[u][v] = w
            dist[v][u] = w
        for u in range(n):
            dist[u][u] = 0
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if dist[i][j] > (d := dist[i][k] + dist[k][j]):
                        dist[i][j] =  d
        neighbors = {len(list(filter(lambda x: 0 < x <= distanceThreshold, dist[i]))): i for i in range(n)}
        return neighbors[min(neighbors)]

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], threshold: int) -> int:
        graph = [[] for i in range(n)]
        for src, dst, weight in edges:
            graph[src].append((weight, dst))
            graph[dst].append((weight, src))

        def find_num_closest(city):
            visited = set()
            q = [(0, city)]
            while q:
                dist, c = heappop(q)
                if c in visited:
                    continue
                visited.add(c)
                for weight, dest in graph[c]:
                    if dist + weight <= threshold:
                        heappush(q, (dist + weight, dest))
            return len(visited)

        min_val = float('inf')
        min_city = None
        for i in range(n):
            closest = find_num_closest(i)
            #print(\"city {} has {} within threshold\".format(i, closest))
            if closest <= min_val:
                min_val = closest
                min_city = i
        return min_city

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        THRESHOLD_MAX = 10001
        dist = [[THRESHOLD_MAX for _ in range(n)] for _ in range(n)]
        
        for edge in edges:
            dist[edge[0]][edge[1]] = edge[2]
            dist[edge[1]][edge[0]] = edge[2]
        
        for i in range(n):
            dist[i][i] = 0
            
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if i != j:
                        intermediate_dist = dist[i][k] + dist[k][j]
                        if intermediate_dist < dist[i][j]:
                            dist[i][j] = intermediate_dist
                            
        min_threshold_cities = n
        curr = -1
        for i in range(n):
            count = 0
            for j in range(n):
                if i != j and dist[i][j] <= distanceThreshold:
                    count +=1
            
            if count <= min_threshold_cities:
                min_threshold_cities = count
                curr = i
        return curr        
            


from collections import defaultdict
class Solution:
    
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        g = [[math.inf] * n for _ in range(n)]
        for i in range(n):
            g[i][i] = 0
        for e in edges:
            g[e[0]][e[1]] = e[2]
            g[e[1]][e[0]] = e[2]
       
\t   # Floyd Warshall's shortest path
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if g[i][j] > g[i][k] + g[k][j]:
                        g[i][j] = g[i][k] + g[k][j]
        res_node, res_connected = -1, math.inf
        for i in range(n):
            conn = 0
            for j in range(n):
                if g[i][j] <= distanceThreshold:
                    conn += 1
            if conn <= res_connected:
                res_node, res_connected = i, conn
        return res_node
            
        

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], D: int) -> int:
        # floyd alg to generate all pairs shortest dists
        dists = [ [ inf for _ in range(n) ] for _ in range(n) ]
        
        for a, b, w in edges:
            dists[a][b] = dists[b][a] = w
        
        for i in range(n):
            dists[i][i] = 0
        
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if dists[i][k] + dists[k][j] < dists[i][j]:
                        dists[i][j] = dists[j][i] = dists[i][k] + dists[k][j] 
        
        # print(dists)
        
        # loop through each node to find all feasible neighbours
        return min(list(range(n)), key = lambda i: (sum(int(d <= D) for d in dists[i]), -i))


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        def method1():
            graph=collections.defaultdict(list)
            for s,d,w in edges:
                graph[s].append((d,w))
                graph[d].append((s,w))
                
            
            def dijkstrase(s):
                queue=[(0,s)]
                seen={s:0}
                
                while queue:
                    w,s=heapq.heappop(queue)
                    for nei,dw in graph[s]:
                        if nei not in seen or w+dw<seen[nei]:
                            seen[nei]=w+dw
                            heapq.heappush(queue, (w+dw,nei))
                
                return seen
            
            distances=[dijkstrase(i) for i in range(n)]
            #print(distances)
            ans=[]
            for i in range(n):
                total=0
                for k,v in list(distances[i].items()):
                    if 0<v<=distanceThreshold:
                        total+=1
                ans.append(total)
                
            #print(ans)
            return max([i for i in range(n) if ans[i]==min(ans)])
            
        return method1()
            
            
                    
                


from collections import defaultdict
class Solution:
    
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        g = [[float('inf')] * n for _ in range(n)]
        for i in range(n):
            g[i][i] = 0
        for e in edges:
            g[e[0]][e[1]] = e[2]
            g[e[1]][e[0]] = e[2]
       
\t   # Floyd Warshall's shortest path
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if g[i][j] > g[i][k] + g[k][j]:
                        g[i][j] = g[i][k] + g[k][j]
        res_node, res_connected = -1, math.inf
        for i in range(n):
            conn = 0
            for j in range(n):
                if g[i][j] <= distanceThreshold:
                    conn += 1
            if conn <= res_connected:
                res_node, res_connected = i, conn
        return res_node
            
        

from typing import List
from collections import defaultdict
from heapq import heappush, heappop

class Solution:
\tdef findTheCityFloydWarshall(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
\t\tdist = [[float('inf')] * n for _ in range(n)]
\t\tfor u, v, w in edges:
\t\t\tdist[u][v] = dist[v][u] = w # bidirectional edges
\t\tfor i in range(n):
\t\t\tdist[i][i] = 0

\t\t# floyd-warshall
\t\tfor k in range(n):
\t\t\tfor i in range(n):
\t\t\t\tfor j in range(n):
\t\t\t\t\tdist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
\t\t
\t\tres = {sum(v <= distanceThreshold for v in dist[u]): u for u in range(n)}
\t\treturn res[min(res)]
\t
\tdef findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
\t\tgraph = defaultdict(dict)
\t\tfor u, v, w in edges:
\t\t\tgraph[u][v] = graph[v][u] = w

\t\tans = [float('inf'), float('inf')]

\t\tfor i in range(n):
\t\t\tpq = [(0, i)]
\t\t\tdist = [float('inf')] * n
\t\t\tdist[i] = 0
\t\t\tvisit = [False] * n

\t\t\twhile pq:
\t\t\t\tdist_u, u = heappop(pq)
\t\t\t\tvisit[i] = True
\t\t\t
\t\t\t\tfor v in graph[u]:
\t\t\t\t\tif not visit[v]:
\t\t\t\t\t\tif dist[v] > dist[u] + graph[u][v]:
\t\t\t\t\t\t\tdist[v] = dist[u] + graph[u][v]
\t\t\t\t\t\t\tif dist[v] <= distanceThreshold:
\t\t\t\t\t\t\t\theappush(pq, (dist[v], v))

\t\t\tcnt = 0
\t\t\tfor d in dist:
\t\t\t\tif d <= distanceThreshold: cnt += 1
\t\t\t
\t\t\tif cnt < ans[0]:
\t\t\t\tans = [cnt, i]
\t\t\telif cnt == ans[0]:
\t\t\t\tif i > ans[1]:
\t\t\t\t\tans = [cnt, i]
\t\t
\t\treturn ans[1]

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        dist = [[float('inf')] * n for _ in range(n)]
        for u, v, w in edges:
            dist[u][v] = w
            dist[v][u] = w
        for u in range(n):
            dist[u][u] = 0
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if dist[i][j] > (d := dist[i][k] + dist[k][j]):
                        dist[i][j] =  d
        ans = {}
        for i,a in enumerate(dist):
            for b in a:
                if(b<=distanceThreshold):
                    if(i in ans):
                        ans[i] +=1
                    else:
                        ans[i] = 1
        ans2 = 0
        minValue = 10000000

        for key, value in list(ans.items()):
            if(value <= minValue):
                minValue = value
                ans2 = key
        return ans2


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
        val = float('inf')
        arr = [[val for i in range(0,n)] for j in range(0,n)]
        
        for x in edges:
            arr[x[0]][x[1]]=x[2]
            arr[x[1]][x[0]]=x[2]
            
        for i in range(0,n):
            arr[i][i]=0
        
        for k in range(0,n):
            for i in range(0,n):
                for j in range(0,n):
                    if arr[i][j] > arr[i][k] + arr[k][j]: 
                        arr[i][j] = arr[i][k] + arr[k][j]
        
        mn = val
        for i in range(0,n):
            count = 0
            for x in arr[i]:
                if x<=distanceThreshold:
                    count+=1
            if count<=mn:
                mn = count
                ret = i
                
        return ret
        
        
        
        


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        g = defaultdict(deque)
        for a,b,d in edges:
            g[a].append((b,d))
            g[b].append((a,d))

        def helper(node:int, threshold) -> int:
            lookup = {}
            heap = [(0,node)]
            visited = set()
            while heap:
                d,u = heapq.heappop(heap)
                if d <= threshold:
                    visited.add(u)
                if d > threshold:
                    return len(visited)
                if u in lookup and lookup[u] < d:
                    continue
                for v,w in g[u]:
                    if v not in lookup or (w+d <= threshold and lookup[v] > w+d):
                        lookup[v] = w+d
                        heapq.heappush(heap,(w+d,v))
            return len(visited)
        min_nei, node = float('inf'), None
        for i in range(n-1,-1,-1):
            count = helper(i, distanceThreshold)
            if count == 1:
                return i
            if count < min_nei:
                min_nei = count
                node = i
        return node
                    


from collections import defaultdict


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        dmatrix = [[9999999999999999 for _ in range(n)] for _ in range(n)]
        
        for a, b, w in edges:
            dmatrix[a][b] = w
            dmatrix[b][a] = w
            
        for source in range(n):
            dmatrix[source][source] = 0
        
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if dmatrix[i][j] > dmatrix[i][k] + dmatrix[k][j]:
                        dmatrix[i][j] = dmatrix[i][k] + dmatrix[k][j]
        
        cities = [(sum([dist <= distanceThreshold for dist in dmatrix[city]]), -city) for city in range(n)]
        _, best_city = list(sorted(cities))[0]
        return -best_city

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        def method1():
            graph=collections.defaultdict(list)
            for s,d,w in edges:
                graph[s].append((d,w))
                graph[d].append((s,w))
                
            
            def dijkstrase(s):
                queue=[(0,s)]
                seen={s:0}
                
                while queue:
                    w,s=heapq.heappop(queue)
                    for nei,dw in graph[s]:
                        if nei not in seen or w+dw<seen[nei]:
                            seen[nei]=w+dw
                            heapq.heappush(queue, (w+dw,nei))
                
                return seen
            
            distances=[dijkstrase(i) for i in range(n)]
            ans=[sum(0<v<=distanceThreshold for k,v in list(distances[i].items())) for i in range(n)]
            return max([i for i in range(n) if ans[i]==min(ans)])
            
        return method1()
            
            
                    
                


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        def method1():
            graph=collections.defaultdict(list)
            for s,d,w in edges:
                graph[s].append((d,w))
                graph[d].append((s,w))
                
            
            def dijkstrase(s):
                queue=[(0,s)]
                seen={s:0}
                
                while queue:
                    w,s=heapq.heappop(queue)
                    for nei,dw in graph[s]:
                        if nei not in seen or w+dw<seen[nei]:
                            seen[nei]=w+dw
                            heapq.heappush(queue, (w+dw,nei))
                
                return seen
            
            distances=[dijkstrase(i) for i in range(n)]
            ans=[]
            for i in range(n):
                total=0
                for k,v in list(distances[i].items()):
                    if 0<v<=distanceThreshold:
                        total+=1
                ans.append(total)
                
            ans=[sum(0<v<=distanceThreshold for k,v in list(distances[i].items())) for i in range(n)]
            return max([i for i in range(n) if ans[i]==min(ans)])
            
        return method1()
            
            
                    
                


'''
Using Floyd-Warshall Algorithm
Reference: https://www.youtube.com/watch?v=oNI0rf2P9gE

TC: O(V^3)
SC: O(V^2)
'''
import heapq
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        dist = [[float('inf')]*n for _ in range(n)]
        graph = defaultdict(list)
        for u, v, w in edges:
            #graph[u].append((w,v))
            #graph[v].append((w,u))
            dist[u][v] = w
            dist[v][u] = w
            dist[u][u] = 0
            dist[v][v]
        
        minCities = n
        ans = -1
        
        '''
        Considering all paths between i, j going through each k vertex
        '''
        for k in range(n):
            for i in range(n):
                numCities = 0
                for j in range(n):
                    if dist[i][j] > dist[i][k] + dist[k][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
                    
                    if k == n-1:
                        if dist[i][j] <= distanceThreshold:
                            numCities += 1
                
                if k == n-1:
                    if numCities <= minCities:
                        ans = i
                        minCities = numCities
        
        return ans
                    


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        graph = [[] for _ in range(n)]
        for i, j, w in edges:
            graph[i].append((j, w))
            graph[j].append((i, w))
        
        result = []
        for i in range(n):
            queue = [(0, i)]
            visited = set()
            while queue:
                distance, i = heapq.heappop(queue)
                if i in visited:
                    continue
                visited.add(i)
                for j, w in graph[i]:
                    new_distance = distance + w
                    if new_distance <= distanceThreshold and j not in visited:
                        heapq.heappush(queue, (new_distance, j))
            result.append(len(visited))
        return min(list(range(n)), key=lambda x: (result[x], -x))
        
        
        
#         dp = [[float(\"inf\")] * n for _ in range(n)]
#         for i in range(n):
#             dp[i][i] = 0
#         for i, j, w in edges:
#             dp[i][j] = w
#             dp[j][i] = w
#         for i in range(n):
#             for j in range(n):
#                 if i != j:
#                     for k in range(j + 1, n):
#                         dp[j][k] = min(dp[j][k], dp[j][i] + dp[i][k])
#                         dp[k][j] = dp[j][k]
#         return min(range(n), key=lambda i: (sum(dist <= distanceThreshold for dist in dp[i]), -i))
        
        
        
#         graph = [[] for _ in range(n)]
#         for i, j, w in edges:
#             graph[i].append((j, w))
#             graph[j].append((i, w))
        
#         result = []
#         for i in range(n):
#             queue = [(0, i)]
#             visited = set()
#             while queue:
#                 distance, i = heapq.heappop(queue)
#                 if i in visited:
#                     continue
#                 visited.add(i)
#                 for j, w in graph[i]:
#                     if distance + w <= distanceThreshold:
#                         heapq.heappush(queue, (distance + w, j))
#             visited.remove(i)
#             result.append(list(visited))
#         return min(range(n), key=lambda x: (len(result[x]), -x))


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        dis = [[float('inf')] * n for _ in range(n) ]
        for u,v,w in edges:
            dis[u][v] = dis[v][u] = w
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if  i != j and dis[i][j] > dis[i][k] + dis[k][j]:
                        dis[i][j] = dis[i][k] + dis[k][j]
        d = {i: len([dis[i][j] for j in range(n) if dis[i][j] <= distanceThreshold]) for i in range(n)}
        minv = float('inf')
        res = -1
        for i in reversed(range(n)):
            if d[i] < minv:
                res = i
                minv = d[i]
        return res

from typing import List
from collections import defaultdict
from heapq import heappush, heappop

class Solution:
\tdef findTheCityFloydWarshall(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
\t\tdist = [[float('inf')] * n for _ in range(n)]
\t\tfor u, v, w in edges:
\t\t\tdist[u][v] = dist[v][u] = w # bidirectional edges
\t\tfor i in range(n):
\t\t\tdist[i][i] = 0

\t\t# floyd-warshall
\t\tfor k in range(n):
\t\t\tfor i in range(n):
\t\t\t\tfor j in range(n):
\t\t\t\t\tdist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
\t\t
\t\tres = {sum(v <= distanceThreshold for v in dist[u]): u for u in range(n)}
\t\treturn res[min(res)]
\t
\tdef findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
\t\tgraph = defaultdict(dict)
\t\tfor u, v, w in edges:
\t\t\tgraph[u][v] = graph[v][u] = w

\t\tans = [float('inf'), float('inf')]

\t\tfor i in range(n):
\t\t\tpq = [(0, i)]
\t\t\tdist = [float('inf')] * n
\t\t\tdist[i] = 0

\t\t\twhile pq:
\t\t\t\tdist_u, u = heappop(pq)
\t\t\t
\t\t\t\tfor v in graph[u]:
\t\t\t\t\tif dist[v] >  dist[u] + graph[u][v]:
\t\t\t\t\t\tdist[v] = dist[u] + graph[u][v]
\t\t\t\t\t\theappush(pq, (dist[v], v))

\t\t\tcnt = 0
\t\t\tfor d in dist:
\t\t\t\tif d <= distanceThreshold: cnt += 1
\t\t\t
\t\t\tif cnt < ans[0]:
\t\t\t\tans = [cnt, i]
\t\t\telif cnt == ans[0]:
\t\t\t\tif i > ans[1]:
\t\t\t\t\tans = [cnt, i]
\t\t
\t\treturn ans[1]

class Solution:
    def dfs(self, q, D, V, k):
        Q = [q]
        V[q] = 0
        while Q:
            T = []
            for nd in Q:
                W = V[nd]
                for n,w in D[nd]:
                    cl = W + w
                    cr = V[n]                
                    if cl < cr and cl <= k:
                        V[n] = cl
                        T.append(n)
            Q = T
        return {a:b for a,b in list(V.items()) if b != sys.maxsize}
    
    def findTheCity(self, N: int, E: List[List[int]], k: int) -> int:
        D = collections.defaultdict(list)
        
        for f,t,w in E:
            D[f].append((t, w))
            D[t].append((f, w))
        
        R = dict()
        mn = sys.maxsize
        for q in range(N):
            V = self.dfs(q, D, collections.defaultdict(lambda:sys.maxsize), k)
            R[q] = V
            if mn > len(V):
                mn = len(V)
            
        R = {a:b for a,b in list(R.items()) if len(b) == mn}
        return max(R.keys())


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
        graph=collections.defaultdict(list)
        for u,v,w in edges:
            graph[u].append([w,v])
            graph[v].append([w,u])
        count=[0]*n
        def find_cities_k(vertex,vis):
            q=[]
            #[distance_covered,vertex]
            heapq.heappush(q,[0,vertex])
            while q:
                dis,node=heapq.heappop(q)
                if node in vis:
                    continue
                vis.add(node)
                if dis<=distanceThreshold:
                    if vertex!=node:
                        count[vertex]+=1
                for w,neigh in graph[node]:
                    if neigh not in vis:
                        heapq.heappush(q,[dis+w,neigh])
        for i in range(n):
            find_cities_k(i,set())
        min_=10000
        city_=-1
        for i in range(n):
            if count[i]<=min_:
                min_=count[i]
                city_=i
        return city_        
            
                        
                
        
                  
        
                
            
            
            


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
        graph = defaultdict(list)
        output = []
        
        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, w))
        
        for i in range(n):
            
            #distance , city 2 , original
            queue = [(0,i)]
            curr = {}
            
            while queue:
                dist, node = heapq.heappop(queue)
                
                if node in curr and dist >= curr[node]:
                    continue
                
                curr[node] = dist
                
                for city, distance in graph[node]:
                    if distance + dist <= distanceThreshold:
                        heapq.heappush(queue,(distance + dist , city))
            
            output.append(len(curr)-1)
        
        for i in range(len(output)-1,-1,-1):
            if output[i] == min(output):
                return i

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        graph = [[] for _ in range(n)]
        for i, j, w in edges:
            graph[i].append((j, w))
            graph[j].append((i, w))
        
        result = []
        for i in range(n):
            queue = [(0, i)]
            distances = defaultdict(lambda: distanceThreshold)
            visited = set()
            while queue:
                distance, i = heapq.heappop(queue)
                if i in visited:
                    continue
                visited.add(i)
                for j, w in graph[i]:
                    new_distance = distance + w
                    if new_distance <= distances[j] and j not in visited:
                        distances[j] = new_distance
                        heapq.heappush(queue, (new_distance, j))
            result.append(len(visited))
        return min(list(range(n)), key=lambda x: (result[x], -x))
        
        
        
#         dp = [[float(\"inf\")] * n for _ in range(n)]
#         for i in range(n):
#             dp[i][i] = 0
#         for i, j, w in edges:
#             dp[i][j] = w
#             dp[j][i] = w
#         for i in range(n):
#             for j in range(n):
#                 if i != j:
#                     for k in range(j + 1, n):
#                         dp[j][k] = min(dp[j][k], dp[j][i] + dp[i][k])
#                         dp[k][j] = dp[j][k]
#         return min(range(n), key=lambda i: (sum(dist <= distanceThreshold for dist in dp[i]), -i))
        
        
        
#         graph = [[] for _ in range(n)]
#         for i, j, w in edges:
#             graph[i].append((j, w))
#             graph[j].append((i, w))
        
#         result = []
#         for i in range(n):
#             queue = [(0, i)]
#             visited = set()
#             while queue:
#                 distance, i = heapq.heappop(queue)
#                 if i in visited:
#                     continue
#                 visited.add(i)
#                 for j, w in graph[i]:
#                     if distance + w <= distanceThreshold:
#                         heapq.heappush(queue, (distance + w, j))
#             visited.remove(i)
#             result.append(list(visited))
#         return min(range(n), key=lambda x: (len(result[x]), -x))


class Solution:
    
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        #22:02-
        
        dists = [[distanceThreshold + 1 for i in range(n)] for j in range(n)]
        for s, e, w in edges:
            dists[s][e] = w
            dists[e][s] = w
        
        for i in range(n):
            dists[i][i] = 0        
        
        #모든 쌍의 최단 거리
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if dists[i][k] + dists[k][j] > distanceThreshold:
                        continue
                    elif dists[i][j] is None:
                        dists[i][j] = dists[i][k] + dists[k][j]
                    elif dists[i][k] + dists[k][j] < dists[i][j]:
                        dists[i][j] = dists[i][k] + dists[k][j]
    
        #smallest number of neighbors
        mn = n
        city = None
        for i in range(n):
            cnt = len([j for j in dists[i] if j <= distanceThreshold])
            if cnt <= mn:
                mn = cnt
                city = i
        return city


from typing import *
from collections import defaultdict
import heapq


class BreakIt(Exception):
    pass


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        G = self.construct_graph(edges)
        # start from n --> 1, keep a track of smallest num of neighbours, prempt if some node has more than smallest num of neighbours found so far
        smallest_neigh_count = float(\"inf\")
        smallest_neigh_node = None
        for i in range(n - 1, -1, -1):
            valid_n = set()
            q = []
            heapq.heappush(q, (0, i))
            visited = set()
            shortest_distance_i = dict()
            try:
                while len(q) > 0:
                    d, curr_n = heapq.heappop(q)
                    visited.add(curr_n)
                    for n, nd in G[curr_n]:
                        old_d = self.relax_distance(shortest_distance_i, n, d + nd)
                        found_shorter_path = old_d > d + nd
                        if d + nd <= distanceThreshold and n != i:
                            valid_n.add(n)
                        if len(valid_n) >= smallest_neigh_count:
                            raise BreakIt
                        if n not in visited or found_shorter_path:
                            heapq.heappush(q, (d + nd, n))
                if len(valid_n) < smallest_neigh_count:
                    smallest_neigh_count = len(valid_n)
                    smallest_neigh_node = i
            except BreakIt:
                pass
        return smallest_neigh_node

    @staticmethod
    def relax_distance(distance_map, d, dist):
        curr_d = distance_map.get(d, float(\"inf\"))
        if dist < curr_d:
            distance_map[d] = dist
        return curr_d

    @staticmethod
    def construct_graph(edges):
        G = defaultdict(set)
        for e in edges:
            n1, n2, w = e
            G[n1].add((n2, w))
            G[n2].add((n1, w))
        return G


import itertools as it


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        inf = float(\"inf\")
        dp = [[inf] * n for _ in range(n)]
        
        for i in range(n):
            dp[i][i] = 0
        
        for a, b, w in edges:
            dp[a][b] = min(dp[a][b], w)
            dp[b][a] = min(dp[b][a], w)
            
        for k, j , i in it.permutations(range(n), 3):
            if i < j:
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
                dp[j][i] = dp[i][j]
            
        out = min([(sum(1 for r in row if r <= distanceThreshold), -i) for i, row in enumerate(dp)])
        
        return -out[1]
        

import collections
import sys


class Solution(object):
    def findTheCity(self, n, edges, distanceThreshold):
        \"\"\"
        :type n: int
        :type edges: List[List[int]]
        :type distanceThreshold: int
        :rtype: int
        \"\"\"

        total = sum([r[2] for r in edges])

        if distanceThreshold >= total:
            return n - 1

        MAX_INT = 10001
        dist = [[MAX_INT] * n for _ in range(n)]

        for i in range(n):
            dist[i][i] = 0

        for i, j, d in edges:
            dist[i][j] = dist[j][i] = d

        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if dist[i][k] == MAX_INT or dist[k][j] == MAX_INT:
                        continue

                    if dist[i][j] > dist[i][k] + dist[k][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]

        res = 0
        min_cnt = n + 1

        for i, row in enumerate(dist):
            cnt = 0
            for j in range(n):
                if dist[i][j] <= distanceThreshold:
                    cnt += 1

                if cnt > min_cnt:
                    break

            if cnt <= min_cnt:
                min_cnt = cnt
                res = i

        return res


import sys
from heapq import heappush, heappop
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
      def shortestPath(adj, V, src, k):
        heap = []
        dist = [sys.maxsize]*V
        dist[src] = 0
        
        heappush(heap,(0,src))
        
        while heap:
          u = heappop(heap)[1]
          
          for node in adj[u]:
            v = node[0]
            weight = node[1]
            
            if dist[v]>dist[u] + weight:
              dist[v] = dist[u] + weight
              heappush(heap, (dist[v],v))
        
        count = 0 
        for d in dist:
          if d<=k:
            count+=1
        
        return count
      
      adj = collections.defaultdict(list)
      
      for val in edges:
        adj[val[0]].append((val[1],val[2]))
        adj[val[1]].append((val[0],val[2]))
            
      cities = [0]*n
      
      for i in range(n):
        cities[i] = shortestPath(adj, n, i, distanceThreshold)
      
      minVal = cities[0]
      minIndex = 0
      
      for i in range(1,n):
        if cities[i]<=minVal:
          minVal = cities[i]
          minIndex = i
            
      return minIndex

from collections import defaultdict
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], cap: int) -> int:
        graph=defaultdict(list)
        
        for i in edges:
            graph[i[0]].append([i[1],i[2]])
            graph[i[1]].append([i[0],i[2]])
            
        # print(graph)
        self.ans=-1
        self.mi=float('inf')
        def bfs(parent):
            seen={parent:-1}
            q=[(parent,0)]
            while(q!=[]):
                tem_node,used=q.pop(0)
                for node,dist in graph[tem_node]:
                    if((node not in seen or dist+used<seen[node]) and (dist+used)<=cap):
                        q.append((node,dist+used))
                        seen[node]=dist+used
            if(self.mi>len(seen)):
                self.mi=len(seen)
                self.ans=parent
            elif(self.mi==len(seen) and parent>self.ans):
                self.ans=parent
        
        for i in range(n):
            bfs(i)
            
        return self.ans
        
        
        
        
        
#         di=dict()
#         for i in range(n):
#             di[i]=set()
        
#         print(graph)
#         # self.mi=float('inf')
#         # self.node=-1
#         def dfs(node,thres,covered,parent):
#             if(thres<0):
#                 return
#             di[parent].add(node)
#             for i in graph[node]:
#                 dfs(i[0],thres-i[1],covered+1,parent)
            
        
#         for i in range(n):
#             dfs(i,distanceThreshold,0,i)
#         ans=-1
#         mi=float('inf')
#         print(di)
#         for i,j in di.items():
#             if(len(j)-1<mi):
#                 mi=len(j)-1
#                 ans=i
#             elif(len(j)-1==mi):
#                 ans=i
#         return ans
        
        
        # return self.node


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
        
        tb = [[float('inf')] * n for _ in range(n)]
        for i in range(n):
            tb[i][i] = 0
        
        for f, t, c in edges:
            tb[f][t] = tb[t][f] = c
        
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if i == j: continue
                    if tb[i][k] + tb[k][j] < tb[i][j]:
                        tb[i][j] = tb[i][k] + tb[k][j]
                        
        i = -1
        c = n+1
        for j in range(n):
            cc = sum(1 for x in tb[j] if x <= distanceThreshold)
            # print(j, cc)
            if cc <= c:
                i = j
                c = cc
        # print(tb)
        return i

'''
Using Dijkstra's Algorithm

Idea:
1) Do Dijkstra from every node due to the weights are non-negative
2) For each city calculate the number of reachable cities within the threshold, then search for the optimal city.

'''
import heapq
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
        graph = defaultdict(list)
        for u, v, w in edges:
            graph[u].append((w,v))
            graph[v].append((w,u))
        
        dist = [[float('inf')]*n for _ in range(n)]
        minCities = n
        ans = -1
        
        for i in range(n):
            q = [(0,i)]
            validCities = 0
            
            while q:
                #print(q)
                distance, node = heapq.heappop(q)
                if distance < dist[i][node]:
                    dist[i][node] = distance
                    if distance <= distanceThreshold:
                        validCities += 1
                else:
                    continue
                
                for neigh in graph[node]:
                    if distance + neigh[0] < dist[i][neigh[1]]:
                        heapq.heappush(q, (distance + neigh[0], neigh[1]))
            
            if validCities <= minCities:
                minCities = validCities
                ans = i
            
        #print(dist)
        #print(ans)
        return ans

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        G = [[] for _ in range(n)]
        
        for u, v, w in edges:
            G[u].append((v, w))
            G[v].append((u, w))
        
        cnt = [0]*n
        
        for i in range(n):
            dist = [10**18]*n
            dist[i] = 0
            pq = [(dist[i], i)]
            
            while pq:
                d, v = heappop(pq)
                
                if dist[v]<d:
                    continue
                    
                for nv, w in G[v]:
                    if dist[nv]>dist[v]+w:
                        dist[nv] = dist[v]+w
                        heappush(pq, (dist[nv], nv))
            
            for j in range(n):
                if dist[j]<=distanceThreshold:
                    cnt[i] += 1
        
        M = 10**18
        
        for i in range(n):
            if M>=cnt[i]:
                M = cnt[i]
                ans = i
        
        return ans

from collections import defaultdict
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], cap: int) -> int:
        graph=defaultdict(list)
        
        for i in edges:
            graph[i[0]].append([i[1],i[2]])
            graph[i[1]].append([i[0],i[2]])
            
        print(graph)
        self.ans=-1
        self.mi=float('inf')
        def bfs(parent):
            seen={parent:-1}
            q=[(parent,0)]
            while(q!=[]):
                tem_node,used=q.pop(0)
                for node,dist in graph[tem_node]:
                    if((node not in seen or dist+used<seen[node]) and (dist+used)<=cap):
                        q.append((node,dist+used))
                        seen[node]=dist+used
            if(self.mi>len(seen)):
                self.mi=len(seen)
                self.ans=parent
            elif(self.mi==len(seen) and parent>self.ans):
                self.ans=parent
        
        for i in range(n):
            bfs(i)
            
        return self.ans
        
        
        
        
        
#         di=dict()
#         for i in range(n):
#             di[i]=set()
        
#         print(graph)
#         # self.mi=float('inf')
#         # self.node=-1
#         def dfs(node,thres,covered,parent):
#             if(thres<0):
#                 return
#             di[parent].add(node)
#             for i in graph[node]:
#                 dfs(i[0],thres-i[1],covered+1,parent)
            
        
#         for i in range(n):
#             dfs(i,distanceThreshold,0,i)
#         ans=-1
#         mi=float('inf')
#         print(di)
#         for i,j in di.items():
#             if(len(j)-1<mi):
#                 mi=len(j)-1
#                 ans=i
#             elif(len(j)-1==mi):
#                 ans=i
#         return ans
        
        
        # return self.node


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        MAX_VAL = 1e6 + 1
        self.graph = [[MAX_VAL for _ in range(n)] for _ in range(n)]
        for idx in range(n): self.graph[idx][idx] = 0
        for edge in edges:
            self.graph[edge[0]][edge[1]] = edge[2]
            self.graph[edge[1]][edge[0]] = edge[2]
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if self.graph[i][k] + self.graph[k][j] < self.graph[i][j]:
                        self.graph[i][j] = self.graph[i][k] + self.graph[k][j]
        results = []
        for idx in range(n):
            results.append((idx, len([_ for _ in range(n) if self.graph[idx][_] <= distanceThreshold])))
        return sorted(results, key=lambda x: (x[1], -x[0]))[0][0]

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        graph = collections.defaultdict(set)
        for u, v, weight in edges:
            graph[u].add((v, weight))
            graph[v].add((u, weight))
  
        dic = {}
        for num in range(n):
            queue = [(num, 0)]
            visited = {num:-1}
            while queue:
                node, total_weight = queue.pop(0)
                for nei, weight in graph[node]:
                    if total_weight + weight <= distanceThreshold and (nei not in visited or total_weight + weight < visited[nei]):
                        queue.append((nei, total_weight + weight))
                        visited[nei] = total_weight + weight
                        
            dic[num] = len(visited)
            
        return sorted(list(dic.items()), key = lambda x: (x[1], -x[0]))[0][0]


from typing import List
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        city_dist_threshold = [float('inf')] * n
        dist_matrix = []

        for index in range(n):
            dist_matrix.append([float('inf')] * n)

        for i,j,weight in edges:
            dist_matrix[i][j] = weight
            dist_matrix[j][i] = weight
        for i in range(n):
            dist_matrix[i][i] = 0
            
        for k_index in range(n):
            for i_index in range(n):
                for j_index in range(n):
                    if i_index == k_index or k_index == j_index or i_index == j_index:
                        continue
                    if dist_matrix[i_index][j_index] > dist_matrix[i_index][k_index] + dist_matrix[k_index][j_index]:
                        dist_matrix[i_index][j_index] = dist_matrix[i_index][k_index] + dist_matrix[k_index][j_index]
                    
        for i_index in range(n):
            for j_index in range(n):
                if dist_matrix[i_index][j_index] <= distanceThreshold:
                    if city_dist_threshold[i_index] == float('inf'):
                        city_dist_threshold[i_index] = 0
                    city_dist_threshold[i_index] += 1
                    
        min_cities, city = min(city_dist_threshold), None
        for index in range(len(city_dist_threshold)):
            if city_dist_threshold[index] == min_cities:
                city = index
        

        return city

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        graph = collections.defaultdict(set)
        for u, v, weight in edges:
            graph[u].add((v, weight))
            graph[v].add((u, weight))
            
        print(graph)
        dic = {}
        for num in range(n):
            #print('num', num)
            queue = [(num, 0)]
            visited = {num:-1}
            count = 0
            while queue:
                node, total_weight = queue.pop(0)
                #print(node, total_weight)
                for nei, weight in graph[node]:
                    if total_weight + weight <= distanceThreshold and (nei not in visited or total_weight + weight < visited[nei]):
                        count += 1
                        queue.append((nei, total_weight + weight))
                        visited[nei] = total_weight + weight
                        
            dic[num] = len(visited)
        print(dic)
        return sorted(list(dic.items()), key = lambda x: (x[1], -x[0]))[0][0]


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        graph = collections.defaultdict(dict)
        
        for i,j,d in edges:
            graph[i][j] = graph[j][i] = d
                   
        def dikstra(node, distanceThreshold):
            visited = [False]*n
            dist = [float('inf')]*n
            heap = [(0, node)]
            
            while not all(visited) and heap:
                distance, node = heapq.heappop(heap)
                if distance > distanceThreshold:
                    break
                    
                dist[node] = distance
                visited[node] = True
                
                for d in graph[node]:
                    if not visited[d]:
                        heapq.heappush(heap, (distance+graph[node][d], d))
            
            return len([i for i in dist if i<=distanceThreshold])
        
        
        
        res = 0
        count = n
        for i in range(n):
            c = dikstra(i, distanceThreshold)
            if c <= count:
                res = max(res,i)
                count = c
        
        return res


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        dis = [[float('inf')] * n for _ in range(n)]
        for i, j, w in edges:
            dis[i][j] = dis[j][i] = w
        for i in range(n):
            dis[i][i] = 0
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
        res = {sum(d <= distanceThreshold for d in dis[i]): i for i in range(n)}
        return res[min(res)]

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        #Dijkstra solution from https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/discuss/536542/Python3-Easy-Readable-Dijkstra
        #Time Complexity: Dijkstra on one vertex is O(ElogV), so for all vertices is O(VElogV), The description says 1 <= edges.length <= n * (n - 1) / 2, so O(E) = O(V^2), Therefore, the final time complexity is O(V^3logV) which should be slower than Floyd Warshall (O(V^3)), comment from https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/discuss/490283/Java-PriorityQueue-%2B-BFS
        graph = collections.defaultdict(list)
        
        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, w))
            
        def getNumberOfNeighbors(city):
            heap = [(0, city)]
            dist = {}
            
            while heap:
                currW, u = heapq.heappop(heap)
                if u in dist: #visited, skip it
                    continue
                if u != city:    
                    dist[u] = currW
                for v, w in graph[u]:
                    if v in dist:
                        continue
                    if currW + w <= distanceThreshold: #find new reacheable city
                        heapq.heappush(heap, (currW + w, v))
            return len(dist)
        
        return max([(getNumberOfNeighbors(city), city) for city in range(n)], key=lambda x: (-x[0], x[1]))[-1]

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        distance = [[float('inf') for _ in range(n)] for _ in range(n)]
        
        for i, j, w in edges:
            distance[i][j] = w
            distance[j][i] = w
        
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
        
        m = collections.defaultdict()
        ans = 0
        
        
        for i in range(n):
            temp = 0
            for j in range(n):
                if distance[i][j] <= distanceThreshold and i != j:
                    temp += 1
            m[temp] = i
        return m[min(m.keys())]

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        graph = collections.defaultdict(list)
        res = float('inf')
        min_city = 0
        for u, v, w in edges:
            graph[u].append(( w, v))
            graph[v].append((w, u))
        def djikstra(node):
            distance = {nid: float('inf') for nid in list(graph.keys())}
            distance[node] = 0
            heap = [(0, node)]
            heapq.heapify(heap)
            total = 0
            while heap:
                d, nd = heapq.heappop(heap)
                if d > distance[nd]:
                    continue
                for nei in graph[nd]:
                    nei_cost, nei_id = nei
                    total = (d + nei_cost)
                    if total < distance[nei_id]:
                        distance[nei_id] = total
                        heapq.heappush(heap, (total, nei_id))
            return sum(dis <= distanceThreshold for dis in list(distance.values()))  - 1
        #print(graph.keys())
        res = {djikstra(i):i for i in range(n)}
        return res[min(res)]
        
        
                       


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        connect = defaultdict(dict)
        ansheap = []
        for a,b,c in edges:
            connect[a][b]=c
            connect[b][a]=c
        for i in range(n):
            dist ={}
            heap = [(0,i)]
            while heap:
                d, u = heapq.heappop(heap)
                if d>distanceThreshold:
                    break
                if u not in dist:
                    dist[u]=d
                    for v in connect[u]:
                        heapq.heappush(heap, (d+connect[u][v],v))
            heapq.heappush(ansheap, (len(dist), -i))
        return - ansheap[0][1]


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        graph = [[] for _ in range(n)]
        for i, j, w in edges:
            graph[i].append((j, w))
            graph[j].append((i, w))
        
        result = []
        for i in range(n):
            queue = [(0, i)]
            visited = set()
            while queue:
                distance, i = heapq.heappop(queue)
                if i in visited:
                    continue
                visited.add(i)
                for j, w in graph[i]:
                    if distance + w <= distanceThreshold:
                        heapq.heappush(queue, (distance + w, j))
            visited.remove(i)
            result.append(list(visited))
        return min(range(n), key=lambda x: (len(result[x]), -x))

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        distDict = defaultdict(dict)
        citySet = set(list(range(n)))
        visitedDict = defaultdict(dict)
        stack = []
        allEdge = 0
        for a, b, w in edges:
            distDict[a][b] = w
            distDict[b][a] = w
            allEdge += w
            if a in citySet:
                citySet.remove(a)
                heapq.heappush(stack, (-distanceThreshold, a, a))
                visitedDict[a][a] = distanceThreshold
            if b in citySet:
                citySet.remove(b)
                heapq.heappush(stack, (-distanceThreshold, b, b))
                visitedDict[b][b] = distanceThreshold
        
        if len(citySet) > 0:
            return max(citySet)
        
        if distanceThreshold > allEdge:
            return n-1
        
        while stack:
            dLeft, source, curr = heapq.heappop(stack)
            dLeft *= -1
            # print(dLeft, source, curr)
            for nextCity in distDict[curr]:
                if (nextCity not in visitedDict[source] or visitedDict[source][nextCity] < (dLeft - distDict[curr][nextCity])) and distDict[curr][nextCity] <= dLeft:
                    visitedDict[source][nextCity] = dLeft - distDict[curr][nextCity]
                    heapq.heappush(stack, (-(dLeft - distDict[curr][nextCity]), source, nextCity))
                # elif nextCity not in visitedDict[source] and distDict[curr][nextCity] == dLeft:
                #     visitedDict[source].add(nextCity)
        # print(visitedDict)
        ansMax = float('inf')
        ans = -1
        for city in visitedDict:
            if ansMax > len(visitedDict[city]):
                ansMax = len(visitedDict[city])
                ans = city
            elif ansMax == len(visitedDict[city]):     
                ans = max(ans, city)
        return ans

from math import floor
from math import ceil
from math import sqrt
from collections import deque
import numpy
from _collections import deque
#from _ast import Num # LC doesn't like this
from heapq import *
from typing import List
import random

MOD = int(1e9 + 7)
BASE = 256


class Solution:

    def findTheCity(self, n: int, edges: List[List[int]],
                    distanceThreshold: int) -> int:
        minD = [[-1 for i in range(n)] for i in range(n)]
        for v in range(n):
            minD[v][v] = 0
        for e in edges:
            u = e[0]
            v = e[1]
            w = e[2]
            minD[u][v] = w
            minD[v][u] = w

        for midNode in range(n):
            for u in range(n):
                for v in range(n):
                    fh = minD[u][midNode]
                    sh = minD[midNode][v]
                    if fh >= 0 and sh >= 0:
                        if minD[u][v] < 0 or fh + sh < minD[u][v]:
                            minD[u][v] = fh + sh
        #print(minD)
        ans = 0
        minCnt = n + 1
        for u in range(n):
            cnt = 0
            for v in range(n):
                if minD[u][v] >= 0 and minD[u][v] <= distanceThreshold:
                    cnt += 1
        #   print(u, cnt)
            if cnt <= minCnt:
                minCnt = cnt
                ans = u
        return ans

\"\"\"
n = 4
edges = [[0, 1, 3], [1, 2, 1], [1, 3, 4], [2, 3, 1]]
distanceThreshold = 4
n = 5
edges = [[0, 1, 2], [0, 4, 8], [1, 2, 3], [1, 4, 2], [2, 3, 1], [3, 4, 1]]
distanceThreshold = 2
s = Solution()
print(s.findTheCity(n, edges, distanceThreshold))
\"\"\"

\"\"\"
12:09

first construct the graph

generate shortest paths (within threshold) to each city from each city
return the city with the smallest number of paths (and largest number for tiebreak)

iterate thru cities
0
keep a PQ of the shortest distances to each node
when we arrive at a new node, add the node + distance to queue
0->1
1: 2

0->4
4: 8

1->2
2: 3 + 2
1->4
4: min(8, 2 + 2) = 4

continue until the queue is empty. O(E)

at the end of the traversal, remove all nodes from the list of paths for which dist > threshold O(V)

do this for each vertex in the graph
O((E + V)) * V)

Output: iterate through each list of cities, track min number of cities and choose the largest numbered city with the min.

\"\"\"
from collections import defaultdict, deque
import heapq

class Solution:
    def construct_graph(self, n, edges, thresh):
        graph = defaultdict(dict)
        # Don't need to include the edge if it's greater than the threshold
        for src, dst, weight in edges:
            if weight <= thresh:
                graph[src][dst] = weight
                graph[dst][src] = weight
        return graph
    
    def compute_distances(self, n, city, graph, thresh):
        remain = set(range(n))
        pq = [(city, 0)]
        distances = [float('inf')] * n
        distances[city] = 0
        neighbors = []
        
        # Perform dijkstra's to every other city in the graph
        while pq:
            curr, dist = heapq.heappop(pq)
            
            # Update distances to neighbors
            for adj, weight in graph[curr].items():
                temp = weight + dist
                if temp < distances[adj]:
                    distances[adj] = temp
                    heapq.heappush(pq, (adj, temp))
        
        # Return all nodes that are within the distance threshold
        for neighbor, dist in enumerate(distances):
            if neighbor != city and dist <= thresh:
                neighbors.append(neighbor)
                
        return neighbors
        
            
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        graph = self.construct_graph(n, edges, distanceThreshold)
        neighbors = {}
        
        # Compute each city's distances to each neighboring city
        for city in range(n):
            neighbors[city] = self.compute_distances(n, city, graph, distanceThreshold)
        
        # print(graph, neighbors)
        min_cities = len(neighbors[0])
        correct_city = 0
        
        # Find the city with smallest number of neighbors
        for city in range(1, n):
            # print(min_cities, correct_city)
            if len(neighbors[city]) <= min_cities:
                min_cities = len(neighbors[city])
                correct_city = city
        
        return correct_city
        

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
        G = collections.defaultdict(list)
        
        for e in edges:
            G[e[0]].append((e[1],e[2]))
            G[e[1]].append((e[0],e[2]))
            
        
        def dfs(i):
            dist = [math.inf]*n
            dist[i]=0
            Queue = collections.deque([(i,0)])
            
            while Queue:
                j,d = Queue.popleft()
                for k in G[j]:
                    if d+k[1]<dist[k[0]] and d+k[1]<=distanceThreshold:
                        dist[k[0]]=d+k[1]
                        Queue.append((k[0],d+k[1]))
            return sum(dist[i]<math.inf for i in range(n))-1
        
        nei = [(dfs(i),-i) for i in range(n)]
        #print(nei)
        heapq.heapify(nei)
        ans = heapq.heappop(nei)
        return -ans[1]
        


class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        #Ford-Faulkerson? Floyd?
        
        dis = [[float('inf')] * n for _ in range(n)]
        
        for i,j,w in edges:
            dis[i][j] = w
            dis[j][i] = w
        
        for i in range(0,n):
            dis[i][i] = 0
        
        for k in range(0,n):
            for i in range(0,n):
                for j in range(0,n):
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
        
        
        nbs = [0]*n
        
        for i in range(0,n):
            nbs[n-1-i] = len([j for j in dis[i] if 0 <j <= distanceThreshold])
            
        
        
        
        return n-1 - nbs.index(min(nbs))

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        distances = [[sys.maxsize] * n for _ in range(n)]

        for src,tar, dis in edges:
            distances[src][tar]=dis
            distances[tar][src]=dis

        for i in range(n):
            distances[i][i]=0

        for k in range(n):
            for i in range(n):
                for j in range(n):
                    distances[i][j]= min (distances[i][j], distances[i][k]+ distances[k][j])


        counts={}
        for i,each in enumerate(distances):
            counts[len([e for e in each if e<=distanceThreshold])]= i

        return counts[min(counts)]

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        #graph init
        maps =[[2**30] * n for _ in range(n)]
        nums_neighbors = [0] * n
        for i in range(n):
            maps[i][i] = 0
        for info in edges:
            src, dst, cost = info
            maps[src][dst] = cost
            maps[dst][src] = cost
            
        for i in range(n):
            for j in range(n):
                for k in range(n):
                    maps[j][k] = min(maps[j][k], maps[j][i] + maps[i][k])
        
        min_idx = 0
        for i in range(n):
            nums_neighbors[i] = len([x for x in maps[i] if x != 0 and x <= distanceThreshold])
            if nums_neighbors[i] <= nums_neighbors[min_idx]:
                min_idx = i
        #print(maps)
        #print(nums_neighbors)
        return min_idx

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], dt: int) -> int:
        dist = [[inf] * n for _ in range(n)]
        
        for f, t, c in edges:
            dist[f][t] = min(dist[f][t], c)
            dist[t][f] = min(dist[t][f], c)
        
        
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        
        arr = []
        for i in range(n):
            cnt = 0
            for j in range(n):
                if i == j or dist[i][j] > dt:
                    continue
                cnt += 1
            arr.append((cnt, -i))
        
        arr.sort()
        return -arr[0][1]