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:\n    def findTheCity(self, n, edges, threshold):\n        adj=[[] for _ in range(n)]\n        for u,v,w in edges:\n            adj[u].append((w,v))\n            adj[v].append((w,u))\n\n        ans=mn=100\n        for x in range(n):\n            cur=1\n            vis={x}\n            dist=[threshold+1]*n\n            hp=[(0,x)]\n            while hp:\n                d,u=heappop(hp)\n                if d>dist[u]:\n                    continue\n                for w,v in adj[u]:\n                    if d+w<dist[v]:\n                        vis.add(v)\n                        dist[v]=d+w\n                        heappush(hp,(d+w,v))\n            if len(vis)<=mn:\n                mn=len(vis)\n                ans=x\n        \n        return ans", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], limit: int) -> int:\n        graph = collections.defaultdict(lambda: [])\n        for n1, n2, w in edges:\n            graph[n1].append((n2, w))\n            graph[n2].append((n1, w))\n        def dijkstra(s):\n            ret = 0\n            dist = [float('inf')]*n\n            dist[s] = 0\n            heap = [(0, s)]\n            seen = set()\n            while heap:\n                cur_w, cur = heapq.heappop(heap)\n                if cur in seen:\n                    continue\n                seen.add(cur)\n                \n                ret += 1\n                for node, w in graph[cur]:\n                    if dist[node] > cur_w+w:\n                        dist[node] = cur_w+w\n                        if dist[node] <= limit:\n                            heapq.heappush(heap, (dist[node], node))\n            return ret-1\n        \n        return sorted([i for i in range(n)], key = lambda x:[dijkstra(x), -x])[0]\n                            \n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:             \n        graph = {i: [] for i in range(n)}\n        # a. create our bidirectional graph with the weights\n        for u, v, w in edges:\n            graph[u].append((v, w))\n            graph[v].append((u, w))\n        # b. loop over the nodes and retain the minimum cities visited\n        res = 0, math.inf\n        for i in range(n):\n            visited = set()\n            q = []\n            heappush(q, (0, i))\n            cities = 0\n            # pop from\n            while q:\n                current_weight, node = heappop(q)\n                if node in visited:\n                    continue\n                visited.add(node)\n                cities += 1\n            # loop over neighbors and append only if not visited and weight <= threshold\n                for neighbor, neighbor_weight in graph[node]:\n                    if neighbor not in visited and current_weight + neighbor_weight <= distanceThreshold:\n                        heappush(q, (current_weight + neighbor_weight, neighbor))\n\n            # when the queue is empty, if cities <= res[1]: res = (i, weight)\n            if cities - 1 <= res[1]:\n                res = i, cities - 1\n\n        return res[0]", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n                \n        # Floyd-warshall\n        \n        dp = [[float('inf') for _ in range(n)] for _ in range(n)]\n        for ed in edges:\n            u, v, weight = ed[0], ed[1], ed[2]\n            dp[u][v] = dp[v][u] = weight\n        \n        for k in range(n):\n            for u in range(n):\n                for v in range(n):\n                    dp[u][v] = min(dp[u][v], dp[u][k] + dp[k][v])\n        \n        ans = -1\n        min_neighbor = float('inf')\n        for u in range(n):\n            cur_neighbor = 0\n            for v in range(n):\n                if v != u and dp[u][v] <= distanceThreshold:\n                    cur_neighbor += 1\n            if cur_neighbor <= min_neighbor:\n                min_neighbor = cur_neighbor\n                ans = u\n        \n        return ans", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        dist = [[float('inf')] * n for _ in range(n)]\n        for u, v, w in edges:\n            dist[u][v] = w\n            dist[v][u] = w\n        for u in range(n):\n            dist[u][u] = 0\n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    if dist[i][j] > (d := dist[i][k] + dist[k][j]):\n                        dist[i][j] =  d\n        neighbors = {len(list([x for x in dist[i] if 0 < x <= distanceThreshold])): i for i in range(n)}\n        return neighbors[min(neighbors)]\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \n        graph=[]\n        \n        for i in range(n):\n            graph.append([float('inf')]*n)                \n        \n        for i in range(n):\n            graph[i][i] = 0\n        \n        for [edge1,edge2, weight] in edges:\n            graph[edge1][edge2] = weight\n            graph[edge2][edge1] = weight\n            \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    graph[i][j] = min(graph[i][j],graph[i][k] + graph[k][j])\n             \n        minNode = -1\n        minCount = 101\n        \n        for i in range(n):\n            count = 0\n            for j in range(n):\n                if(graph[i][j]<=distanceThreshold):\n                    count+=1\n            \n            \n            if count <= minCount:\n                minCount = count\n                minNode = i\n            \n        return minNode\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        distances=[[sys.maxsize] *n for _ in range(n)]\n        \n        for u,v,w in edges:\n            distances[u][v]=w\n            distances[v][u]=w\n            \n        for i in range(n):\n            distances[i][i]=0\n            \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    distances[i][j]=min(distances[i][j], distances[i][k]+distances[k][j])\n                    \n        counts={}\n        \n        for i, dist in enumerate(distances):\n            counts[len([d for d in dist if d<=distanceThreshold])]=i\n        \n        return counts[min(counts)]\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \n        dp = [[float('inf') for _ in range(n)] for _ in range(n)]\n        \n        for s, e, w in edges:\n            dp[s][e] = w\n            dp[e][s] = w\n        \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])\n                    \n                    \n        minlen = n\n        res = -1\n\n        for i, row in enumerate(dp):\n            cnt = sum(v <= distanceThreshold and j != i for j, v in enumerate(row))\n            if cnt <= minlen:\n                minlen = cnt\n                res = i\n                \n        return res", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        paths = []\n        for i in range(n): paths.append([sys.maxsize] * n)\n        \n        # all non edges are inf\n        # all self paths are 0\n        for src,dest,weight in edges:\n            paths[src][dest] = weight\n            paths[dest][src] = weight\n        for i in range(n): paths[i][i] = 0\n      \n        # calculate all source shortest paths\n        for k in range(n):\n            for src in range(n):\n                for dest in range(n):\n                    paths[src][dest] = min(paths[src][dest], paths[src][k] + paths[k][dest])\n\n        globalNode = -1\n        globalReachable = sys.maxsize\n\n        for i in range(n):\n            localNode = i\n            localReachable = 0\n            \n            for j in range(n):\n                if paths[i][j] <= distanceThreshold and j != i: \n                    localReachable += 1\n                \n            if localReachable < globalReachable: \n                globalReachable = localReachable\n                globalNode = localNode\n\n            elif localReachable == globalReachable and localNode > globalNode:\n                globalNode = localNode\n                \n        return globalNode\n", "from typing import List\nfrom collections import defaultdict\n\nclass Solution:\n\\tdef findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n\\t\\tdist = [[float('inf')] * n for _ in range(n)]\n\\t\\tfor u, v, w in edges:\n\\t\\t\\tdist[u][v] = dist[v][u] = w # bidirectional edges\n\\t\\tfor i in range(n):\n\\t\\t\\tdist[i][i] = 0\n\n\\t\\t# floyd-warshall\n\\t\\tfor k in range(n):\n\\t\\t\\tfor i in range(n):\n\\t\\t\\t\\tfor j in range(n):\n\\t\\t\\t\\t\\tdist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])\n\\t\\t\n\\t\\tprint(dist)\n\n\\t\\tres = {sum(v <= distanceThreshold for v in dist[u]): u for u in range(n)}\n\\t\\t\n\\t\\treturn res[min(res)]", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        d = [[float('inf') for _ in range(n)] for _ in range(n)]\n\n        # Floyd Warshall\n        # bases cases\n        for s, t, w in edges:\n            d[s][t] = w\n            # add in opposite\n            d[t][s] = w\n\n        # get all paths from node\n        for i in range(n):\n            for s in range(n):\n                for t in range(n):\n                    d[s][t] = min(d[s][t], d[s][i] + d[i][t])\n\n        neighbors = [0 for i in range(n)]\n        for s in range(n):\n            for t in range(n):\n                if s != t and d[s][t] <= distanceThreshold:\n                    neighbors[s] += 1\n\n        min_value = float('inf')\n        res = None\n\n        for v in range(n):\n            if neighbors[v] <= min_value:\n                min_value = neighbors[v]\n                res = v\n\n        return res\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        dis=[[float(inf)] * n for _ in range(n)]\n        for i,j,w in edges:\n            dis[i][j]=w\n            dis[j][i]=w\n        for i in range(n):\n            dis[i][i] = 0\n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j])\n        \n        res = {sum(d<=distanceThreshold for d in dis[i]) : i for i in range(n)}\n        print(res)\n        return res[min(res)]\n        \n        ''' 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)\n        d = collections.defaultdict(list)\n        lookup = dict({})\n        for e in edges:\n            s, e, l = e[0], e[1], e[2]\n            d[s].append(e)\n            d[e].append(s)\n            lookup[(s,e)]=l\n            lookup[(e,s)]=l\n        \n        res=collections.defaultdict(list)\n        def dfs(j: int, i:int, t:int, v:set):\n\n            for c in d[i]:\n                if c not in v and c != j and lookup[(i,c)] <= t:\n                    res[j].append(c)\n                    v.add(c)\n                    dfs(j, c, t-lookup[i,c], v)\n                \n        \n        for i in range(n):\n            dfs(i, i, distanceThreshold, set({}))\n        if n > 26:\n            print(\\\"27={},33={}\\\".format(res[27], res[33]))\n        mm = len(res[0])\n        r = 0\n        for i in range(n):\n            print(\\\"{},len:{}\\\".format(i, len(res[i])))\n            if len(res[i])  <= mm:\n                r = i\n                mm = len(res[i])\n        return r\n        '''", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \n        graph = collections.defaultdict(list)\n        \n        for u, v, w in edges:\n            graph[u].append((v, w))\n            graph[v].append((u, w))\n            \n        dist = collections.defaultdict(list)\n        self.min = float('inf')\n        def getNumberOfNeighbors(city):\n            heap = [(0, city)]\n            count = 0\n            seen = set()\n            while heap:\n                currW, u = heapq.heappop(heap)\n                if u in seen:\n                    continue\n                seen.add(u)\n                for v, w in graph[u]:\n                    if v in seen:\n                        continue\n                    if currW + w <= distanceThreshold:\n                        heapq.heappush(heap, (currW + w, v))\n                count += 1\n            return count\n        \n        for city in range(n):\n            num = getNumberOfNeighbors(city)\n            dist[num].append(city)\n            self.min = min(self.min, num)\n        \n        return max(dist[self.min])", "class Solution:\n    def findTheCity2(self, n: int, edges: List[List[int]], dt: int) -> int:\n        \\\"\\\"\\\"Floyd-warshall, O(n^3)\\\"\\\"\\\"\n        dist = [[float('inf')] * n for _ in range(n)]\n        for i in range(n):\n            dist[i][i] = 0\n        for u, v, w in edges:\n            dist[u][v] = w\n            dist[v][u] = w\n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])\n        res, con = -1, float('inf')\n        for i in range(n):\n            cur = sum(dist[i][j] <= dt for j in range(n))\n            if cur <= con:\n                con = cur\n                res = i\n        return res\n    \n    def findTheCity(self, n: int, edges: List[List[int]], dt: int) -> int:\n        g = collections.defaultdict(list)\n        for u, v, w in edges:\n            g[u].append((v, w))\n            g[v].append((u, w))\n        def dijkstra(src):\n            pq = [(0, src)]\n            seen = set()\n            res = 0\n            while pq:\n                d, cur = heapq.heappop(pq)\n                if d > dt or cur in seen:\n                    continue\n                seen.add(cur)\n                res += 1\n                for nei, nw in g[cur]:\n                    if nei not in seen:\n                        heapq.heappush(pq, (d + nw, nei))\n            return res\n        dp = [dijkstra(i) for i in range(n)]\n        mn = float('inf')\n        res = -1\n        for i, num in enumerate(dp):\n            if num <= mn:\n                mn = num\n                res = i\n        return res\n        \n                \n        \n                        ", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n#         FLOYD WARSHALL \n            \n        dist = [[float('inf') for j in range(n)] for i in range(n)]\n        \n        for edge in edges:\n            dist[edge[0]][edge[1]] = edge[2]\n            dist[edge[1]][edge[0]] = edge[2]\n        \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])\n        \n        curr = 0\n        res_idx = 0\n        count = float('inf')\n        \n        for i in range(n):\n            curr = 0\n            for j in range(n):\n                if i!=j and dist[i][j] <= distanceThreshold:\n                    curr += 1\n            \n            if curr <= count:\n                count = curr\n                res_idx = i\n        \n        return res_idx\n        \n        \n        \n", "class Solution:\n    def findTheCity(self, n, edges, maxd):\n        \\\"\\\"\\\"\n        * dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])\n        # res = {sum(d <= maxd for d in dis[i]): i for i in range(n)}\n        \\\"\\\"\\\"\n        \n        \\\"\\\"\\\"\n        \u57ce\u5e02i\u5230\u57ce\u5e02j\u7684\u8ddd\u96e2\u77e9\u9663:\n        [[0, 2, 5, 5, 4], \n         [2, 0, 3, 3, 2], \n         [5, 3, 0, 1, 2], \n         [5, 3, 1, 0, 1], \n         [4, 2, 2, 1, 0]]\n        \\\"\\\"\\\"\n        dis = [[float('inf')] * n for _ in range(n)] # \u57ce\u5e02i\u5230\u57ce\u5e02j\u7684\u8ddd\u96e2\u77e9\u9663\n        for i, j, w in edges:\n            dis[i][j] = dis[j][i] = w\n        \n        for i in range(n):\n            dis[i][i] = 0\n        \n        # ### wrong!\n        # for i in range(n):\n        #     for j in range(n):\n        #         for k in range(n):\n        \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])\n        \n        res = {sum(d <= maxd for d in dis[i]): i for i in range(n)} # {\u6578\u76ee: \u57ce\u5e02}\n        return res[min(res)]", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        INF=9999999\n        dist=[[INF for j in range(n)] for i in range(n)]\n        graph=[[]for i in range(n)]\n        for e in edges:\n            i=e[0]\n            j=e[1]\n            dist[i][j]=e[2]\n            dist[j][i]=e[2]\n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    if i!=j:\n                        dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])\n        #print(dist)\n        ans=-1\n        mm=n\n        for i in range(n):\n            k=0\n            for j in range(n):\n                if dist[i][j]<=distanceThreshold:\n                    k+=1\n            if k<=mm:\n                mm=k\n                ans=i\n        return ans", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n \n        dist = [ [math.inf]*n  for _ in range(n) ]\n        for i,j,w in edges:\n            dist[i][j] = w\n            dist[j][i] = w\n        \n        for i in range(n):\n            dist[i][i] = 0\n        \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])\n        \n        res = []\n        for i in range(n):\n            res.append( sum( dist[i][j]<=distanceThreshold for j in range(n) ) )\n        \n        print(res)\n        \n        tmp = (n, 0)\n        for i,c in enumerate(res):\n            # print(tmp)\n            if (c,-i) < tmp:\n                tmp = (c,-i)\n            \n        return -tmp[1]\n        \n        \n        \n        \n        \n#         graph = collections.defaultdict(list)\n#         for i,j,w in edges:\n#             graph[i].append([j,w])\n#             graph[j].append( [i, w] )\n        \n        \n#         res = [0]*n\n        \n#         for i in range(n):\n#             print('start')\n#             print(i)\n#             visited = set([i])\n#             que = collections.deque([ (i,0) ])\n#             while que:\n#                 cur, dist = que.popleft()\n#                 for j,w in graph[cur]:\n#                     print([j, dist+w] )\n#                     if j not in visited and dist+w<=distanceThreshold:\n                        \n#                         visited.add(j)\n#                         que.append( [j,dist+w ] )\n#                         res[i]+=1\n        \n#         # print(res)\n        \n#         m = min(res)\n#         for i in range(n-1, -1, -1):\n#             if res[i] == m:\n#                 return i\n            \n                        \n        \n        \n", "from collections import defaultdict\n\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        cityGraph = [[float(\\\"inf\\\") for col in range(n)] for row in range(n)]\n        for edge in edges:\n            cityGraph[edge[0]][edge[1]] = edge[2]\n            cityGraph[edge[1]][edge[0]] = edge[2]\n            \n        \n        for intermediateCity in range(n):\n            for startCity in range(n):\n                for endCity in range(n):\n                    if startCity != endCity:\n                        cityGraph[startCity][endCity] = min(cityGraph[startCity][endCity], cityGraph[startCity][intermediateCity]+cityGraph[intermediateCity][endCity])\n        \n        cityThresholdSum = [sum(1 for cityDist in city if cityDist <= distanceThreshold) for city in cityGraph]\n        \n        return len(cityThresholdSum) - 1 -cityThresholdSum[::-1].index(min(cityThresholdSum))", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        # \u6784\u5efadist\u77e9\u9635\n        dist = [[float('inf')] * n for _ in  range(n)]\n        for i, j, w in edges:\n            dist[i][j] = w\n            dist[j][i] = w\n        for i in range(n):\n            dist[i][i] = 0\n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])\n\n        # \u8fc7\u6ee4\n        res = 0\n        minCnt = float('inf')\n        for i in range(n):\n            cnt = 0\n            for d in dist[i]:\n                if d <= distanceThreshold:\n                    cnt += 1\n            if cnt <= minCnt:\n                minCnt = cnt\n                res = i\n        return res\n", "def buildGraph(n, edges):\n    graph = [[float('inf')]*n for _ in range(n)]\n    for e in edges:\n        graph[e[0]][e[1]] = e[2]\n        graph[e[1]][e[0]] = e[2]\n\n    '''\n    Floyed-Warshall algorithm won't work if diagonal values are not set to \n    0 when self loop distance is not given\n    '''\n    for i in range(n):\n        graph[i][i] = 0\n    \n    return graph\ndef floyedWarshalAllPairDist(graph):\n    n = len(graph)\n    for i in range(n):\n        for j in range(n):\n            for k in range(n):\n                graph[j][k] = min(graph[j][k], graph[j][i]+graph[i][k])\n    \n'''\nAlgorithm: \n1) Measure all pair distance using Floyed Warshal algorithm\n2) Find the city with minimum connected cities with atmost threshold distance\n'''\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \n        '''\n        graph = buildGraph(n, edges)\n        floyedWarshalAllPairDist(graph)\n        \n        min_city = 0\n        min_count = float('inf')\n        for i in range(n):\n            count = sum([1 if x<=distanceThreshold else 0 for x in graph[i]])\n            if count <= min_count:\n                min_count = count\n                min_city = i\n        \n        return min_city\n        '''\n        g = [[float('inf')]*n for _ in range(n)]\n        for u,v,w in edges:\n            g[u][v] = w\n            g[v][u] = w\n        \n        for i in range(n):\n            for u in range(n):\n                for v in range(n):\n                    if u==v: \n                        g[u][v]=0\n                    else:\n                        g[u][v] = min(g[u][v], g[u][i]+g[i][v])\n        \n        city, count = -1,float('inf')\n        for i in range(n):\n            tmp = sum(1 for x in g[i] if x<=distanceThreshold)\n            if tmp<=count:\n                city = i\n                count = tmp\n        \n        return city\n        \n        \n        \n        \n        \n", "import sys\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        dist = arr = [[10001 if i!=j else 0 for i in range(n)] for j in range(n)]\n        \n        for source, target, weight in edges:\n            dist[source][target] = weight\n            dist[target][source] = weight\n        \n        # implementing floyd-warshall\n        for node in range(n):\n            for source in range(n):\n                for target in range(n):\n                    new_dist = dist[source][node] + dist[node][target]\n                    #if source == target: new_dist = 0\n                    dist[source][target] = min(dist[source][target], new_dist)\n                    \n        #print(dist)\n        ncity = [n]*n\n        for dindex, dlist in enumerate(dist):\n            ncity[dindex] = [index for index, i in enumerate(dlist) if i <= distanceThreshold and i != 0]\n            \n        for source, cities in enumerate(ncity):\n            for target in cities:\n                if source not in ncity[target]: ncity[target].append(source)\n                    \n        #print(ncity)\n        min_count = 10001\n        index = 0\n        for cindex, city in enumerate(ncity):\n            len_city = len(city)\n            if len_city <= min_count:\n                min_count = len_city\n                index = cindex\n        return index", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        def dij(arr, i):\n            passed = [i]\n            notpass = [j for j in range(len(arr)) if j != i ]\n            dis = arr[i]\n            while notpass:\n                index = notpass[0]\n                for node in notpass:\n                    if dis[node] < dis[index]:\n                        index = node\n                passed.append(index)\n                notpass.remove(index)\n                \n                for x, total in enumerate(dis):\n                    dis[x] = min(dis[x], dis[index] + arr[index][x])\n            return dis\n                    \n            \n        arr = [[float('inf') for x in range(n)] for y in range(n)]  \n        for i in range(n):\n            arr[i][i] = 0\n            \n        for fromi, toj, val in edges:\n            arr[fromi][toj] = val\n            arr[toj][fromi] = val\n            \n        min_nums, min_indexes = float('inf'), []\n        for i in range(n):\n            dis = dij(arr, i)\n            nums = len([length for length in dis if length <= distanceThreshold])\n            if nums < min_nums:\n                min_nums = nums\n                min_indexes = [i]\n            elif nums == min_nums:\n                min_indexes.append(i)\n                \n        return max(min_indexes)\n            \n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \\\"\\\"\\\"priority queue + bfs \\\"\\\"\\\"\n        graph = defaultdict(list)\n        for st, ed, w in edges:\n            graph[st].append((w, ed))\n            graph[ed].append((w, st))\n\n        opt = float(\\\"inf\\\")\n        ans = 0\n        for i in range(n):\n            cnt = self.numofNeighbor(n, graph, distanceThreshold, i)            \n            if cnt <= opt:\n                ans, opt = i, cnt\n        return ans\n\n    def numofNeighbor(self, n, graph, distancTreshold, node):\n        queue = []\n        queue.append((0, node))\n        visited = [False for _ in range(n)]\n        cnt = 0\n        while queue:\n            w, v = heappop(queue)\n            if visited[v]:\n                continue\n            cnt += 1\n            visited[v] = True\n\n            for d, neighbor in graph[v]:\n                if visited[neighbor]:\n                    continue\n                if d + w > distancTreshold:\n                    continue\n                heappush(queue, (w+d, neighbor))\n\n        return cnt", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        storage = [[30000 if i != j else 0 for i in range(n) ] for j in range(n)]\n        for edge in edges:\n            storage[edge[0]][edge[1]] = edge[2]\n            storage[edge[1]][edge[0]] = edge[2]\n        \n        #FloydWarshallAPSP\n        for k in range(0, n):\n            for i in range(0, n):\n                for j in range(0, n):\n                    currD = storage[i][j]\n                    toK = storage[i][k]\n                    fromK = storage[k][j]\n                    storage[i][j] = min(storage[i][j], toK + fromK)\n        \n        #Process to get answer\n        currLowestCity = 0\n        currLowestCount = 200\n        for i in range(0, n):\n            count = 0\n            for j in range(0, n):\n                if storage[j][i] <= distanceThreshold:\n                    count += 1\n            if count <= currLowestCount:\n                currLowestCity = i\n                currLowestCount = count\n        \n        return currLowestCity\n", "class Solution:\n    \n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        dp = [[float('inf')]*n for _ in range(n)]\n        for i, j, w in edges:\n            dp[i][j] = dp[j][i] = w\n        for i in range(n):\n            dp[i][i] = 0\n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])\n        min_idx, min_val = None, None\n        for i in range(n):\n            can_val = sum(v <= distanceThreshold for v in dp[i])\n            if min_val is None or can_val <= min_val:\n                min_val = can_val\n                min_idx = i\n        return min_idx \n        \n        \n        \n        \n        \n            \n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        storage = [[30000 if i != j else 0 for i in range(n) ] for j in range(n)]\n        for edge in edges:\n            storage[edge[0]][edge[1]] = edge[2]\n            storage[edge[1]][edge[0]] = edge[2]\n        \n        #FloydWarshallAPSP\n        for k in range(0, n):\n            for i in range(0, n):\n                for j in range(0, n):\n                    currD = storage[i][j]\n                    toK = storage[i][k]\n                    fromK = storage[k][j]\n                    storage[i][j] = min(storage[i][j], toK + fromK)\n                    \n        print(\\\"storage\\\", storage)\n        \n        #Process to get answer\n        currLowestCity = 0\n        currLowestCount = 200\n        for i in range(0, n):\n            count = 0\n            for j in range(0, n):\n                if storage[j][i] <= distanceThreshold:\n                    count += 1\n            if count <= currLowestCount:\n                currLowestCity = i\n                currLowestCount = count\n        \n        return currLowestCity\n", "from collections import defaultdict\nclass Solution:\n    \n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        dis = [[float('inf')] * n for _ in range(n)]\n        for i, j, w in edges:\n            dis[i][j] = dis[j][i] = w\n        for i in range(n):\n            dis[i][i] = 0\n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])\n        res = {sum(d <= distanceThreshold for d in dis[i]): i for i in range(n)}\n        return res[min(res)]\n        \n            \n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        graph=[[99999 for j in range(n)]for k in range(n)]\n        dict1={}\n        for u,v,w in edges:\n            graph[u][v]=w\n            graph[v][u]=w\n        for i in range(n):\n            graph[i][i]=1\n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    graph[i][j]=min(graph[i][j],graph[i][k]+graph[k][j])\n        ans=-1\n        min1=999999999\n        for i in range(n):\n            count=0\n            for j in range(n):\n                if(graph[i][j] <= distanceThreshold):\n                    count+=1\n            #print(count)\n            if(count <= min1):\n                min1=count\n                ans=i\n        return ans\n", "class Solution:\n    \n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        dp = [[float('inf')]*n for _ in range(n)]\n        for i, j, w in edges:\n            dp[i][j] = dp[j][i] = w\n        for i in range(n):\n            dp[i][i] = 0\n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])\n        res = {sum(v <= distanceThreshold for v in dp[i]): i for i in range(n)}\n        return res[min(res)]\n        \n        \n        \n        \n        \n            \n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        AdjMat = [[float('inf')] * n for _ in range(n)]\n        \n        for i in range(n):\n            AdjMat[i][i] = 0\n            \n        for u,v,w in edges:\n            AdjMat[u][v] = w\n            AdjMat[v][u] = w\n            \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    AdjMat[i][j] = min(AdjMat[i][j],AdjMat[i][k] + AdjMat[k][j])\n                    \n        d = {}\n        for i in range(n):\n            c = -1\n            for j in range(n):\n                if AdjMat[i][j] <= distanceThreshold:\n                    c += 1\n                    \n            d[i] = c\n            \n        m = min(d.values())\n        res = 0\n        for k in d:\n            if d[k] == m:\n                res = max(res,k)\n        return res\n                \n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        adj = [[float('inf')] * n for i in range(n)]\n        \n        for i in range(n):\n            adj[i][i] = 0\n        \n        for u,v,w in edges:\n            adj[u][v] = w\n            adj[v][u] = w\n            \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j])\n                    \n        print(adj)\n        \n        res = float('inf')\n        res_city = -1\n        for i in range(n):\n            count = 0\n            for j in range(n):\n                if i != j:\n                    if adj[i][j] <= distanceThreshold:\n                        count += 1                        \n            if count <= res:\n                res = count\n                res_city = i\n            \n        return res_city\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        dis = [[float('inf')] * n for _ in range(n)]\n        \n        for i, j, w in edges:\n            dis[i][j] = dis[j][i] = w\n            \n        for i in range(n):\n            dis[i][i] = 0\n            \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])\n        \n        print(dis)\n        ans = 0\n        mmin = n\n        for i in range(n):\n            count = 0\n            for j in range(n):\n                if dis[i][j] <= distanceThreshold:\n                    count += 1\n            if count <= mmin:\n                mmin = count\n                ans = i\n        return ans", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        # Floyd-Warshall: shortest path between all pairs of vertices, negative edges allowed\n        # Dijkstra's: shortest path from one node to all nodes\n        # Bellman-Ford: shortest path from one node to all nodes, negative edges allowed\n        dis = [[float('inf') for _ in range(n)] for _ in range(n)]\n        for i, j, w in edges:\n            dis[i][j] = dis[j][i] = w\n        for i in range(n):\n            dis[i][i] = 0\n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j])\n        # res = {sum(d <= distanceThreshold for d in dis[i]): i for i in range(n)}\n        res = {}\n        for i in range(n):\n            count = 0\n            for d in dis[i]:\n                if d <= distanceThreshold:\n                    count += 1\n            res[count] = i\n\n        return res[min(res)]\n        \n        # Dijkstra\n#         weight = collections.defaultdict(dict)\n#         for u, v, w in edges:\n#             weight[u][v] = w\n#             weight[v][u] = w\n        \n#         def getNumberOfNeighbors(city):\n#             heap = [(0, city)]\n#             dist = {}\n            \n#             while heap:\n#                 w, u = heapq.heappop(heap)\n#                 if u not in dist and u != city:\n#                     dist[u] = w\n#                 for v in weight[u]:\n#                     if v in dist:\n#                         continue\n#                     if w + weight[u][v] <= distanceThreshold:\n#                         heapq.heappush(heap, (w+weight[u][v], v))\n#             return len(dist)\n#         minCount = float('inf')\n#         ans = None\n#         for i in range(n):\n#             count = getNumberOfNeighbors(i)\n#             if count <= minCount:\n#                 ans = i\n#                 minCount = count\n#         return ans\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        graph = collections.defaultdict(list)\n        res = float('inf')\n        min_city = 0\n        for u, v, w in edges:\n            graph[u].append(( w, v))\n            graph[v].append((w, u))\n        def djikstra(node):\n            distance = {nid: float('inf') for nid in list(graph.keys())}\n            distance[node] = 0\n            heap = [(0, node)]\n            heapq.heapify(heap)\n            total = 0\n            while heap:\n                d, nd = heapq.heappop(heap)\n                if d > distance[nd]:\n                    continue\n                for nei in graph[nd]:\n                    nei_cost, nei_id = nei\n                    total = (d + nei_cost)\n                    if total < distance[nei_id]:\n                        distance[nei_id] = total\n                        heapq.heappush(heap, (total, nei_id))\n            return sum(dis <= distanceThreshold for dis in list(distance.values()))  - 1\n        res = {djikstra(i):i for i in range(n)}\n        return res[min(res)]\n        \n        \n                       \n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        # Floyd-Warshall: shortest path between all pairs of vertices, negative edges allowed\n        # Dijkstra's: shortest path from one node to all nodes\n        # Bellman-Ford: shortest path from one node to all nodes, negative edges allowed\n        dis = [[float('inf') for _ in range(n)] for _ in range(n)]\n        for i, j, w in edges:\n            dis[i][j] = dis[j][i] = w\n        for i in range(n):\n            dis[i][i] = 0\n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j])\n        # res = {sum(d <= distanceThreshold for d in dis[i]): i for i in range(n)}\n        res = {}\n        for i in range(n):\n            count = 0\n            for d in dis[i]:\n                if d <= distanceThreshold:\n                    count += 1\n            res[count] = i\n\n        return res[min(res)]", "class Solution:\n    def findTheCity(self, N: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \n        dist = [[float('inf')] * N for _ in range(N)]\n        \n        for u in range(N):\n            dist[u][u] = 0\n            \n        for u, v, w in edges:\n            dist[u][v] = w\n            dist[v][u] = w\n            \n        # Floyd\n        for k in range(N):\n            for j in range(N):\n                for i in range(N):\n                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])\n        \n        # Calculate\n        min_cities = float('inf')\n        ret = None\n        print(dist)\n        \n        for u in range(N):\n            reach = 0\n            for v in range(N):\n                if u != v and dist[u][v] <= distanceThreshold:\n                    reach += 1\n            \n            if reach <= min_cities:\n                min_cities = reach\n                ret = u\n                \n        return ret\n            \n        \n", "class Solution:\n    def findTheCity(self, n, edges, maxd):\n        \\\"\\\"\\\"\n        * dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])\n        # res = {sum(d <= maxd for d in dis[i]): i for i in range(n)}\n        \\\"\\\"\\\"\n        dis = [[float('inf')] * n for _ in range(n)]\n        for i, j, w in edges:\n            dis[i][j] = dis[j][i] = w\n        for i in range(n):\n            dis[i][i] = 0\n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])\n        res = {sum(d <= maxd for d in dis[i]): i for i in range(n)}\n        return res[min(res)]\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n\n        matrix = [[float('inf') for x in range(n)] for y in range(n)]\n        \n        # populate self loops\n        for i in range(n):\n            matrix[i][i] = 0\n        \n        # populate initial matrix\n        for u,v,w in edges:\n            matrix[u][v] = w\n            matrix[v][u] = w\n\n        # floyd-warshall       \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    matrix[i][j] = min(matrix[i][j], matrix[i][k]+matrix[k][j])                  \n        \n        # get amount of below threshold cities\n        res = Counter()\n        for i, row in enumerate(matrix):\n            for j, dist in enumerate(row):\n                if dist <= distanceThreshold and i != j :\n                    res[i] += 1\n        \n        best = 0\n        for i in range(n):\n            if res[i] <= res[best]:\n                best = i\n        return best\n        \n        # check if unconnected cities\n        unconnected = []\n        i = 0\n        while i < n:\n            if res[i] == 0:\n                # not conencted\n                unconnected.append(i)\n            i += 1\n                \n        if len(unconnected) == 1:\n            return unconnected[0]\n        elif len(unconnected) > 1:\n            return max(unconnected)\n            \n        # all cities are connected with each other, get min value\n        ans = min(res.values())\n        max_city = 0\n        \n        # if multiple cities with same minimum neighbours, select biggest one\n        for city in range(len(res)):\n            if res[city] <= ans and city > max_city:\n                max_city = city\n                \n\n        return max_city", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        dis = [[9999999] * n for _ in range(n)]\n        \n        for i, j, w in edges:\n            dis[i][j] = dis[j][i] = w\n        for i in range(n):\n            dis[i][i] = 0\n        \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])\n        print(dis)\n        \n        m, ans = n, 0\n        for i in range(n):\n            c = 0\n            for j in range(n):\n                if(dis[i][j] <= distanceThreshold):\n                    c += 1\n            if(c <= m):\n                ans = i\n                m = c\n        return ans    \n                \n                \n", "import heapq\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        graph = []\n        for _ in range(n):\n            graph.append([float('inf')]*n)\n        \n        for i,j,w in edges:\n            graph[i][j] = w\n            graph[j][i] = w\n        \n        \n        nums = []\n        for i in range(n):\n            ans = self.dijkstra(graph, i, distanceThreshold)\n            nums.append(ans)\n        \n        ans = 0\n        minW = float('inf')\n        for i, w in enumerate(nums):\n            if w <= minW:\n                minW = w\n                ans = i\n        return ans\n            \n        \n    def dijkstra(self, graph, idx, threshold):\n        dist = [(w, i) for i,w in enumerate(graph[idx]) if w != float('inf')]\n        heapq.heapify(dist)\n        ans = []\n        visited = {idx}\n        while len(dist) > 0 and dist[0][0] <= threshold and len(visited) <= len(graph):\n            cur_w, i = heapq.heappop(dist)\n            if i not in visited:\n                ans.append(i)\n                visited.add(i)\n                for j, w in enumerate(graph[i]):\n                    if w != float('inf'):\n                        heapq.heappush(dist, (w+cur_w,j))\n        return len(ans)\n            \n            \n            \n", "class Solution:\n    def dfs(self, q, D, V, k):\n        Q = [q]\n        V[q] = 0\n        while Q:\n            T = []\n            for nd in Q:\n                W = V[nd]\n                for n,w in D[nd]:\n                    cl = W + w\n                    cr = V[n]                \n                    if cl < cr and cl <= k:\n                        V[n] = cl\n                        T.append(n)\n            Q = T\n        return {a:b for a,b in V.items() if b != sys.maxsize}\n    \n    def findTheCity(self, N: int, E: List[List[int]], k: int) -> int:\n        D = collections.defaultdict(list)\n        \n        for f,t,w in E:\n            D[f].append((t, w))\n            D[t].append((f, w))\n        \n        R = dict()\n        mn = sys.maxsize\n        for q in range(N):\n            V = self.dfs(q, D, collections.defaultdict(lambda:sys.maxsize), k)\n            R[q] = V\n            if mn > len(V):\n                mn = len(V)\n            \n        R = {a:b for a,b in R.items() if len(b) == mn}\n        return max(R.keys())", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \n        dp = [[float(\\\"inf\\\")] *n for _ in range(n)]\n        \n        for i,j,w in edges:\n            dp[i][j] = dp[j][i] = w\n            \n        for i in range(n):\n            dp[i][i] = 0\n            \n        for i in range(n):\n            for j in range(n):\n                for k in range(n):\n                    dp[j][k] = min(dp[j][k] , dp[j][i] + dp[i][k])\n                    \n        res = { sum(d <= distanceThreshold for d in dp[i]) : i for i in range(n) }\n        \n        return res[min(res)]\n    \n        \n        \n        ", "'''\nIdea is that we figure out for each city i all cities with index larger than i are reachable with distance at most distanceThreshold.\n'''\nimport heapq\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        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.\n        edgeWeights = defaultdict(dict)\n        for start,end,weight in edges:\n            edgeWeights[start][end] = weight\n            edgeWeights[end][start] = weight\n        def computeDistances(i):##we will compute minimum distance for all vertices from i.\n            iHeap = []\n            heapq.heapify(iHeap)##remember you create list first and then heapify.\n            heapq.heappush(iHeap,(0,i))\n            visited = set()##need to ensure we don't go back and forth\n            while iHeap:\n                distance,vertex = heapq.heappop(iHeap)\n                if vertex in visited:##don't want to expand a vertex if we already found its minimum distance\n                    continue\n                if distance > distanceThreshold:\n                    break\n                else:\n                    distances[i][vertex] = distance##we know this vertex has to have closest distance to i\n                    visited.add(vertex)##this is when we know we have found minimum distance\n                    for neighbor in edgeWeights[vertex]:\n                        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.\n                            continue\n                        edgeWeight = edgeWeights[vertex][neighbor]\n                        heapq.heappush(iHeap,(distance+edgeWeight,neighbor))\n        lowestNumber = n\n        lowestCity = -1\n        for i in range(n):\n            computeDistances(i)\n            if len(distances[i]) <= lowestNumber:\n                lowestNumber = len(distances[i])\n                lowestCity = i\n        ##print(distances)\n        return lowestCity\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], limit: int) -> int:\n        dist = [[float(\\\"inf\\\")]*n for _ in range(n)]\n        for n1, n2, w in edges:\n            dist[n1][n2] = w\n            dist[n2][n1] = w\n        \n        for i in range(n):\n            dist[i][i] = 0\n        \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])\n        \n        ans = {sum(dist[i][j] <= limit for j in range(n)):i for i in range(n)}\n        return ans[min(ans)]\n                            \n            ", "from typing import List\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        city_dist_threshold = [float('inf')] * n\n        dist_matrix = []\n\n        for index in range(n):\n            dist_matrix.append([float('inf')] * n)\n        for i in range(n):\n            dist_matrix[i][i] = 0\n\n        for i,j,weight in edges:\n            dist_matrix[i][j] = weight\n            dist_matrix[j][i] = weight\n        \n        for k_index in range(n):\n            for i_index in range(n):\n                for j_index in range(n):\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])\n                    \n        for i_index in range(n):\n            for j_index in range(n):\n                if dist_matrix[i_index][j_index] <= distanceThreshold:\n                    if city_dist_threshold[i_index] == float('inf'):\n                        city_dist_threshold[i_index] = 0\n                    city_dist_threshold[i_index] += 1\n\n        min_cities, city = min(city_dist_threshold), None\n        for index in range(len(city_dist_threshold)):\n            if city_dist_threshold[index] == min_cities:\n                city = index\n        \n\n        return city", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        mark = [[float('inf') for i in range(n)] for j in range(n)]\n        for i in range(n):\n            mark[i][i]=0\n        for i,j ,w in  edges:\n            mark[i][j]=w\n            mark[j][i]=w\n        for node in range(n):\n            for i in range(n):\n                for j in range(n):\n                    if i!=j:\n                        mark[i][j] = min(mark[i][j],mark[i][node]+mark[node][j])\n                    #if i==4 and j==0 and node==5:\n                        #print(mark[i][node]+mark[node][j])\n        #print(mark)\n        cnt = n\n        ans= -1\n        for i in range(n):\n            cur=0\n            for j in range(n):\n                if i!=j and mark[i][j]<=distanceThreshold:\n                    cur+=1\n            #print(cur)\n            #print(cnt)\n            if cur<=cnt: \n                #print(cur,cnt)\n                cnt=cur\n                ans= i\n                #print(cur,cnt,ans)\n        return ans\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], threshold: int) -> int:\n        graph = defaultdict(list)\n        for u, v, w in edges:\n            graph[u].append((v, w))\n            graph[v].append((u, w))\n        \n        def dijkstra(initial_node):\n            dist = [float('inf')] * n\n            dist[initial_node] = 0\n            \n            pq = [(initial_node, 0)]\n            while pq:\n                node, d = heappop(pq)\n                \n                for adjnode, weight in graph[node]:\n                    if dist[adjnode] > dist[node] + weight:\n                        dist[adjnode] = dist[node] + weight\n                        pq.append((adjnode, dist[node]))\n            return dist\n        \n        city_num = 0 # ans city number\n        cc = n + 1 # cities connected\n        for node in range(n):\n            dist = dijkstra(node)\n            print(dist)\n            c = -1\n            for d in dist:\n                if d <= threshold:\n                    c += 1\n\n            if c <= cc:\n                print(c)\n                cc = c\n                city_num = node\n\n        return city_num\n", "import math\n\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        distance=[[math.inf for i in range(n)] for j in range(n)]\n        for i in edges:\n            distance[i[0]][i[1]]=i[2]\n            distance[i[1]][i[0]]=i[2]\n            \n        for i in range(n):\n            for j in range(n):\n                if i!=j and distance[i][j]!=math.inf:\n                    for k in range(n):\n                        if k!=i:\n                            d=distance[i][j]+distance[j][k]\n                            if d<distance[i][k]:\n                                distance[i][k]=d\n                                # print(i,j,k)\n                                # print(\\\"\\\n\\\")\n                            \n        for i in range(n):\n            for j in range(n):\n                if i!=j and distance[i][j]!=math.inf:\n                    for k in range(n):\n                        if k!=i:\n                            d=distance[i][j]+distance[j][k]\n                            if d<distance[i][k]:\n                                distance[i][k]=d\n                                \n        # print(distance)\n        mini=math.inf\n        for i in range(n):\n            a=0\n            for j in range(n):\n                if distance[i][j]<=distanceThreshold:\n                    a+=1\n            # print(a)\n            if a<=mini:\n                mini=a\n                city=i\n                \n        return city", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \n        dist = [[float('inf')] * n for _ in range(n)]\n        for i in range(n):\n            dist[i][i] = 0\n        for pair in edges:\n            a, b, c = pair\n            dist[a][b] = dist[b][a] = c\n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])\n                        \n        res = {}\n        \n        for i in range(len(dist)):\n            res[sum(x <= distanceThreshold for x in dist[i])] = i\n        \n        return res[min(res)]", "class Solution:\n    \\\"\\\"\\\"\n    Floyd-Warshall\n    \\\"\\\"\\\"\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        dp = [[float('inf')]*n for _ in range(n)]\n        for i in range(n):\n            dp[i][i] = 0\n        \n        for u, v, w in edges:\n            dp[u][v] = w\n            dp[v][u] = w\n        \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    if i == k or j == k:\n                        continue\n                    dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])\n        \n        min_city = n-1\n        min_reachable = float('inf')\n        for i in range(n):\n            reachable = sum([dp[i][dst] <= distanceThreshold for dst in range(n)])\n            if reachable <= min_reachable:\n                min_city = i\n                min_reachable = reachable\n        \n        return min_city", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        import numpy\n        adj = [[float('inf')]*n for _ in range(n)]\n        \n        for u, v, w in edges:\n            adj[u][v] = adj[v][u] = w\n            \n        for i in range(n):\n            adj[i][i] = 0\n        \n            \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j])\n        print(numpy.matrix(adj))                  \n        \n\n        res = {sum(d <= distanceThreshold for d in adj[i]): i for i in range(n)}\n        print(res)\n        return res[min(res)]", "import collections\nfrom heapq import heappop,heappush\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \n        dist=[[float('inf') for _ in range(n)] for _ in range(n)]\n        graph=collections.defaultdict(list)\n        \n        for u,v,w in edges:\n            dist[u][v]=dist[v][u]=w\n            graph[u].append(v)\n            graph[v].append(u)\n        for i in range(n):\n            dist[i][i]=0\n        visited=set()\n        \n        for i in range(n):\n            stack=[(0,i)]\n            while stack:\n                k,j=heappop(stack)\n                if (i,j) not in visited and k<=distanceThreshold:\n                    visited.add((i,j))\n                    for neigh in graph[j]:\n                        dist[i][neigh]=min(dist[i][neigh],k+dist[j][neigh])\n                        heappush(stack,(dist[i][neigh],neigh))\n        print(dist)\n        ans=None\n        maxi=float('inf')\n        for i in range(n):\n            temp=0\n            for j in range(n):\n                if dist[i][j]<=distanceThreshold:\n                    temp+=1\n            if temp<=maxi:\n                maxi=temp\n                ans=i\n        return ans", "class Solution:\n    def findTheCity(self, n: int, edges, distanceThreshold: int) -> int:\n        matrix = [[float('inf')]*n for _ in range(n)]\n        for s, e, d in edges:\n            matrix[s][e] = d\n            matrix[e][s] = d\n        for i in range(n):\n            matrix[i][i] = 0\n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    matrix[i][j] = min(matrix[i][j], matrix[i][k]+matrix[k][j])\n        res, count = 0, n\n        for i in range(n):\n            tmp = sum(matrix[i][j] <= distanceThreshold for j in range(n))\n            if tmp <= count:\n                count = tmp\n                res = i\n        return res", "from heapq import heappush, heappop\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        dis = [[float('inf')]*n for _ in range(n)]\n        nei = collections.defaultdict(list)\n        for i,j,x in edges:\n            dis[i][j] = dis[j][i] = x\n            nei[i].append(j)\n            nei[j].append(i)\n        for i in range(n):\n            dis[i][i] = 0\n        \n        # Dijkstra\n        visited = set()\n        for i in range(n):\n            pool = [(0,i)]                                          # pool[j] = x:  d(i,j) = x    \n            while pool:\n                x,j = heappop(pool)                                 # x = d(i,j)\n                if (i,j) not in visited and x <= distanceThreshold: # early stop, if distance exceeds threshold\n                    visited.add((i,j))\n                    for k in nei[j]:\n                        dis[i][k] = min(dis[i][k], x+dis[j][k])     # dis(i,k) = min(dis(i,k), dis(i,j)+dis(j,k))\n                        heappush(pool, (dis[i][k], k))\n\n        cities = {sum(d <= distanceThreshold for d in dis[i]):i for i in range(n)}\n        return cities[min(cities)]", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        minDistance = collections.defaultdict(lambda: collections.defaultdict(lambda: math.inf))\n        for i in range(n):\n            minDistance[i][i] = 0\n        \n        for u, v, weight in edges:\n            minDistance[u][v] = weight\n            minDistance[v][u] = weight\n        \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    minDistance[i][j] = min(minDistance[i][j], minDistance[i][k] + minDistance[k][j])\n        \n        minNeighborCount = math.inf\n        minCity = -1\n        \n        for i in range(n):\n            # Count how many of city i's neighbors are within the distance threshold.\n            neighborCount = sum(minDistance[i][j] <= distanceThreshold for j in range(n) if j != i)\n            \n            # Update the result if a city with less neighbors has been found or the id is higher\n            if neighborCount <= minNeighborCount:\n                minNeighborCount = neighborCount\n                minCity = i\n        \n        return minCity", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        storage = [[30000 if i != j else 0 for i in range(n) ] for j in range(n)]\n        for edge in edges:\n            storage[edge[0]][edge[1]] = edge[2]\n            storage[edge[1]][edge[0]] = edge[2]\n        \n        #FloydWarshallAPSP\n        for k in range(0, n):\n            for i in range(0, n):\n                for j in range(0, n):\n                    currD = storage[i][j]\n                    toK = storage[i][k]\n                    fromK = storage[k][j]\n                    storage[i][j] = min(storage[i][j], toK + fromK)\n                    \n        print(\\\"storage\\\", storage)\n        \n        #Process to get answer\n        numCities = [0 for i in range(n)]\n        currLowestCity = 0\n        currLowestCount = 200\n        for i in range(0, n):\n            count = 0\n            for j in range(0, n):\n                if storage[j][i] <= distanceThreshold:\n                    count += 1\n            if count <= currLowestCount:\n                currLowestCity = i\n                currLowestCount = count\n        \n        return currLowestCity\n", "from heapq import heappush, heappop\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        dis = [[float('inf')]*n for _ in range(n)]\n        nei = collections.defaultdict(list)\n        for i,j,x in edges:\n            dis[i][j] = dis[j][i] = x\n            nei[i].append(j)\n            nei[j].append(i)\n        for i in range(n):\n            dis[i][i] = 0\n        \n        # Dijkstra\n        visited = set()\n        for i in range(n):\n            pool = [(0,i)]                                          # pool[j] = x:  d(i,j) = x    \n            while pool:\n                x,j = heappop(pool)                                 # x = d(i,j)\n                if (i,j) not in visited and x <= distanceThreshold: # early stop, if distance exceeds threshold\n                    visited.add((i,j))\n                    for k in nei[j]:\n                        dis[i][k] = min(dis[i][k], x+dis[j][k])     # dis(i,k) = min(dis(i,k), dis(i,j)+dis(j,k))\n                        heappush(pool, (dis[i][k], k))\n\n        cities = {sum(d <= distanceThreshold for d in dis[i]):i for i in range(n)}\n        print(cities)\n        return cities[min(cities)]", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        distance = [[float('inf') for _ in range(n)] for _ in range(n)]\n        \n        for i, j, w in edges:\n            distance[i][j] = w\n            distance[j][i] = w\n        \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])\n        \n        m = collections.defaultdict()\n        ans = 0\n        \n        print(distance)\n        \n        for i in range(n):\n            temp = 0\n            for j in range(n):\n                if distance[i][j] <= distanceThreshold and i != j:\n                    temp += 1\n            m[temp] = i\n        print(m)\n        return m[min(m.keys())]", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], threshold: int) -> int:\n        graph = collections.defaultdict(list)\n        res = [0] * n\n        for a, b, d in edges:\n            graph[a].append([b, d])\n            graph[b].append([a, d])\n        for i in range(n):\n            queue = [[0, i]]\n            visit = set()\n            while queue:\n                t, curr = heapq.heappop(queue)\n                if t <= threshold and curr not in visit:\n                    visit.add(curr)\n                    for nei, dis in graph[curr]:\n                        heapq.heappush(queue, [t + dis, nei])    \n            res[i] = len(visit) - 1\n        return -sorted([[v, -i] for i, v in enumerate(res)])[0][1]", "import itertools as it\n\n\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        inf = float(\\\"inf\\\")\n        dp = [[inf] * n for _ in range(n)]\n        \n        for i in range(n):\n            dp[i][i] = 0\n        \n        for a, b, w in edges:\n            dp[a][b] = min(dp[a][b], w)\n            dp[b][a] = min(dp[b][a], w)\n            \n        for k, j , i in it.permutations(range(n), 3):\n            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])\n            dp[j][i] = dp[i][j]\n            \n        out = min([(sum(1 for r in row if r <= distanceThreshold), -i) for i, row in enumerate(dp)])\n        \n        return -out[1]\n        ", "from collections import defaultdict\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], cap: int) -> int:\n        \n        minDistance = collections.defaultdict(lambda: collections.defaultdict(lambda: float(\\\"inf\\\")))\n        \n        for i in range(n):\n            minDistance[i][i]=0\n        \n        for i,j,w in edges:\n            minDistance[i][j]=w\n            minDistance[j][i]=w\n        \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    minDistance[i][j]=min(minDistance[i][j],minDistance[i][k]+minDistance[k][j])\n        \n        mi=float(\\\"inf\\\")\n        ans=-1\n        \n        for i in range(n):\n            neighCount=sum(minDistance[i][j]<=cap for j in range(n) if j!=i)\n            if(neighCount<=mi):\n                mi=neighCount\n                ans=i\n        return ans\n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n#         graph=defaultdict(list)\n        \n#         for i in edges:\n#             graph[i[0]].append([i[1],i[2]])\n#             graph[i[1]].append([i[0],i[2]])\n            \n#         # print(graph)\n#         self.ans=-1\n#         self.mi=float('inf')\n#         def bfs(parent):\n#             seen={parent:-1}\n#             q=[(parent,0)]\n#             while(q!=[]):\n#                 tem_node,used=q.pop(0)\n#                 for node,dist in graph[tem_node]:\n#                     if((node not in seen or dist+used<seen[node]) and (dist+used)<=cap):\n#                         q.append((node,dist+used))\n#                         seen[node]=dist+used\n#             if(self.mi>len(seen)):\n#                 self.mi=len(seen)\n#                 self.ans=parent\n#             elif(self.mi==len(seen) and parent>self.ans):\n#                 self.ans=parent\n        \n#         for i in range(n):\n#             bfs(i)\n            \n#         return self.ans\n        \n        \n        \n        \n        \n#         di=dict()\n#         for i in range(n):\n#             di[i]=set()\n        \n#         print(graph)\n#         # self.mi=float('inf')\n#         # self.node=-1\n#         def dfs(node,thres,covered,parent):\n#             if(thres<0):\n#                 return\n#             di[parent].add(node)\n#             for i in graph[node]:\n#                 dfs(i[0],thres-i[1],covered+1,parent)\n            \n        \n#         for i in range(n):\n#             dfs(i,distanceThreshold,0,i)\n#         ans=-1\n#         mi=float('inf')\n#         print(di)\n#         for i,j in di.items():\n#             if(len(j)-1<mi):\n#                 mi=len(j)-1\n#                 ans=i\n#             elif(len(j)-1==mi):\n#                 ans=i\n#         return ans\n        \n        \n        # return self.node", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \n        dis = [[float('inf')] * n for _ in range(n)]\n        for i, j, w in edges:\n            dis[i][j] = dis[j][i] = w\n        for i in range(n):\n            dis[i][i] = 0\n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])\n        res = {sum(d <= distanceThreshold for d in dis[i]): i for i in range(n)}\n        return res[min(res)]", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        A = []\n        for i in range(n):\n            A.append([float('inf')]*n)\n        for i in range(len(A)):\n            A[i][i] = 0                    \n        for i in edges:\n            A[i[0]][i[1]] = i[2]\n            A[i[1]][i[0]] = i[2]\n        for k in range(n):\n            for i in range(len(A)):\n                for j in range(len(A[i])):\n                    if i == j or i == k or j == k:\n                        continue\n                    A[i][j] = min(A[i][j],A[i][k]+A[k][j])\n        print(A)\n        minc = float('inf')\n        city = n-1\n        for i in range(len(A)):\n            cnt = 0\n            for j in range(len(A[i])):\n                if A[i][j] <= distanceThreshold:\n                    cnt += 1\n            if cnt <= minc:\n                minc = cnt\n                city = i\n        return city\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], threeshold: int) -> int:\n        class Graph:\n            def __init__(self,vertices):\n                self.v = vertices\n                self.graph = collections.defaultdict(dict)\n\n            def add_edge(self,u,v,cost):\n                self.graph[u][v] = cost\n                self.graph[v][u] = cost\n\n            def calculateDist(self,s,dT):\n                dist = [sys.maxsize]*(self.v)\n                dist[s] = 0\n                unvisited_queue = [[0,s]]\n                visited = [False]*self.v\n                heapq.heapify(unvisited_queue)\n                while len(unvisited_queue) > 0:\n                    u =  heapq.heappop(unvisited_queue)\n                    curr_v = u[1]\n                    visited[curr_v] = True\n                    for neighbour in self.graph[curr_v]:\n                        cost = self.graph[curr_v][neighbour]\n                        if dist[neighbour] > dist[curr_v] + cost:\n                            dist[neighbour] = dist[curr_v] + cost\n                    while len(unvisited_queue) > 0:\n                        heapq.heappop(unvisited_queue)\n                    for node in range(self.v):\n                        if visited[node] == False:\n                            heapq.heappush(unvisited_queue,[dist[node],node])\n                cities = -1\n                for d in dist:\n                    if d <= dT:\n                        cities += 1\n                return cities\n        min_connections = sys.maxsize\n        city = 0\n        v = n\n        graph = Graph(v)\n        for edge in edges:\n            n,m,cost = edge[0],edge[1],edge[2]\n            graph.add_edge(n,m,cost)\n        # print(graph.graph)\n        for i in range(v):\n            cities = graph.calculateDist(i,threeshold)\n            if cities < min_connections:\n                min_connections = cities\n                city = i\n            elif cities == min_connections:\n                city = max(city,i)\n        return city", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        # Start at 11:09PM\n        # Brute force: O(N*(N + E))\n        \n        # Need to make a dictionary holding the edges\n        edges_dict= collections.defaultdict(list)\n        for src,dest,weight in edges:\n            edges_dict[src].append((dest, weight))\n            edges_dict[dest].append((src, weight))\n        \n        # Helper function \n        # Gets input as the node to start from, and distance that can be travelled\n        # returns count of nodes that it can reach\n        \n        import heapq\n        # Need to do book keeping, if can reach given node quicker\n        def get_reachable_count(nd, distance):\n            heap = [(0, nd)]\n            count = 0\n            visited = set()\n            while heap:\n                travelled, nd = heapq.heappop(heap)\n                if nd in visited:\n                    continue\n                \n                visited.add(nd)\n                count += 1\n                for (dest, new_dist) in edges_dict[nd]:\n                    if new_dist + travelled > distance or dest in visited:\n                        continue\n                    heapq.heappush(heap, (new_dist+travelled, dest))\n            return count - 1\n        get_reachable_count(1, distanceThreshold)\n        curr_min_val = float('inf')\n        curr_best_idx = -1\n        for i in range(n):\n            count = get_reachable_count(i, distanceThreshold) \n            # print(\\\"Fin\\\", i, count)\n            if count <= curr_min_val:\n                curr_min_val, curr_best_idx = count, i\n        return curr_best_idx\n                \n                \n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        from heapq import heappush, heappop\n        import collections\n        distance = [[float('inf')] * n for _ in range(n)]\n        graph = collections.defaultdict(list);\n        # initialize the graph and distance matrix\n        for i, j, w in edges:\n            distance[i][j] = distance[j][i] = w\n            graph[i].append(j)\n            graph[j].append(i)\n        for i in range(n):\n            distance[i][i] = 0\n        \n        # use dijkstra algorithm for every node\n        global_min = [-1, -1]\n        for i in range(n):\n            count = 0\n            visited = set()\n            q = [(0, i)]\n            while q:\n                dis, j = heappop(q)\n                if dis <= distanceThreshold:\n                    count += 1\n                if (i, j) not in visited and dis < distanceThreshold:\n                    visited.add((i, j))\n                    for nei in graph[j]:\n                        distance[i][nei] = min(distance[i][nei], dis + distance[j][nei])\n                        heappush(q, (distance[i][nei], nei))\n        global_min = [-1, -1]\n        for i in range(n):\n            count = 0\n            for j in range(n):\n                if distance[i][j] <= distanceThreshold:\n                    count += 1\n                \n            if global_min[0] == -1 or count <= global_min[0]:\n                global_min[0] = count\n                global_min[1] = i\n        \n        return global_min[1]\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        dis = [[float(\\\"inf\\\") ] * n for _ in range(n)]\n        for i in range(n):\n            dis[i][i] = 0\n        for u, v, w in edges:\n            dis[u][v] = dis[v][u] = w\n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])\n        res = -1\n        min_count = float(\\\"inf\\\")\n        for k in range(n-1, -1, -1):\n            count = 0\n            for j in range(n):\n                if dis[k][j] <= distanceThreshold:\n                    count += 1\n            if min_count > count:\n                res = k\n                min_count = count\n        return res", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        from heapq import heappush, heappop\n        import collections\n        distance = [[float('inf')] * n for _ in range(n)]\n        graph = collections.defaultdict(list);\n        # initialize the graph and distance matrix\n        for i, j, w in edges:\n            distance[i][j] = distance[j][i] = w\n            graph[i].append(j)\n            graph[j].append(i)\n        for i in range(n):\n            distance[i][i] = 0\n        \n        # use dijkstra algorithm for every node\n        global_min = [-1, -1]\n        for i in range(n):\n            count = set()\n            visited = set()\n            q = [(0, i)]\n            while q:\n                dis, j = heappop(q)\n                if dis <= distanceThreshold:\n                    count.add(j)\n                if (i, j) not in visited and dis < distanceThreshold:\n                    visited.add((i, j))\n                    for nei in graph[j]:\n                        distance[i][nei] = min(distance[i][nei], dis + distance[j][nei])\n                        heappush(q, (distance[i][nei], nei))\n            # print(count)\n            if global_min[0] == -1 or len(count) <= global_min[0]:\n                global_min[0] = len(count)\n                global_min[1] = i\n        \n        return global_min[1]\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        graph = defaultdict(list)\n        output = []\n        \n        for u, v, w in edges:\n            graph[u].append((v, w))\n            graph[v].append((u, w))\n        \n        queue = deque([])\n        for i in range(n):\n            \n            #distance , node\n            queue.append((i, 0))\n            \n            # current represent a hash map of all of the cities and \n            # their distances from i\n            curr = {}\n            \n            while queue:\n                node, dist = queue.popleft()\n                \n                if node in curr and dist >= curr[node]:\n                    continue\n                \n                curr[node] = dist\n                \n                for nei, newDist in graph[node]:\n                    if newDist + dist <= distanceThreshold:\n                        queue.append((nei, newDist + dist))\n            \n            output.append(len(curr)-1)\n            # print(output)\n        \n        for node in reversed(range(len(output))):\n            if output[node] == min(output):\n                return node", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        dp = [[10001 for j in range(n)] for i in range(n)]\n        for i in range(n):\n            dp[i][i] = 0\n        \n        for u, v, w in edges:\n            dp[u][v] = w\n            dp[v][u] = w\n        \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])\n        \n        l = []\n        smallest = 101\n        for i in range(n):\n            temp = 0\n            for j in range(n):\n                if dp[i][j] <= distanceThreshold:\n                    temp += 1\n                \n            if temp < smallest:\n                smallest = temp\n                l = [i]\n            elif temp == smallest:\n                l.append(i)\n        \n        return l[-1]\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        dis = [[float('inf')]*n for _ in range(n)]\n        nei = collections.defaultdict(list)\n        for i,j,x in edges:\n            dis[i][j] = dis[j][i] = x\n            nei[i].append(j)\n            nei[j].append(i)\n        for i in range(n):\n            dis[i][i] = 0\n        \n        # Dijkstra\n        visited = set()\n        for i in range(n):\n            pool = [(0,i)] \n            while pool:\n                x,j = heapq.heappop(pool)\n                if (i,j) not in visited and x <= distanceThreshold:\n                    visited.add((i,j))\n                    for k in nei[j]:\n                        dis[i][k] = min(dis[i][k], x+dis[j][k])\n                        heapq.heappush(pool, (dis[i][k], k))\n\n        cities = {sum(d <= distanceThreshold for d in dis[i]):i for i in range(n)}\n        return cities[min(cities)]", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        mat=[]\n        for _ in range(n):\n            mat.append([float('inf')]*n)\n            \n        for i,j,d in edges:\n            mat[i][j]=d\n            mat[j][i]=d\n        \n        for i in range(n):\n            mat[i][i]=0\n            \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    mat[i][j]=min(mat[i][j],mat[i][k]+mat[k][j])\n        \n        res=[]\n        for i in range(n):\n            res.append(sum(1 for x in mat[i] if x<=distanceThreshold))\n        \n        s=float('inf')\n        for i in range(n):\n            if res[i] <=s:\n                s=res[i]\n                out=i\n                \n        return out", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        dis = [[float('inf')]*n for _ in range(n)]\n        nei = collections.defaultdict(list)\n        for i,j,x in edges:\n            dis[i][j] = dis[j][i] = x\n            nei[i].append(j)\n            nei[j].append(i)\n        for i in range(n):\n            dis[i][i] = 0\n        \n        # Dijkstra\n        visited = set()\n        for i in range(n):\n            pool = [(0,i)]                                          # pool[j] = x:  d(i,j) = x    \n            while pool:\n                x,j = heapq.heappop(pool)                                 # x = d(i,j)\n                if (i,j) not in visited and x <= distanceThreshold: # early stop, if distance exceeds threshold\n                    visited.add((i,j))\n                    for k in nei[j]:\n                        dis[i][k] = min(dis[i][k], x+dis[j][k])     # dis(i,k) = min(dis(i,k), dis(i,j)+dis(j,k))\n                        heapq.heappush(pool, (dis[i][k], k))\n\n        cities = {sum(d <= distanceThreshold for d in dis[i]):i for i in range(n)}\n        return cities[min(cities)]", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        A = [[float('inf')]*n for _ in range(n)]\n        for i in range(n):\n            A[i][i] = 0\n        for x, y, w in edges:\n            A[x][y] = w\n            A[y][x] = w\n            \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    A[i][j] = min(A[i][j], A[i][k] + A[k][j])\n                \n        res = -1        \n        val = float('inf')\n        for i in range(n):\n            t = sum([d <= distanceThreshold for d in A[i]])\n            if t <= val:\n                val = t\n                res = i\n        return res", "from heapq import heappush, heappop\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \n        def dijkstra(graph, start, distance):\n            reached = set()\n            heap = [(0, start)]\n            while heap:\n                w, node = heappop(heap)\n                if node in reached:\n                    continue\n                if w > distance:\n                    continue\n                if node != start:\n                    reached.add(node)\n                for nex, nex_w in graph[node]:\n                    heappush(heap, (w + nex_w, nex))\n            return len(reached)\n        \n        graph = collections.defaultdict(set)        \n        for x,y,w in edges:\n            graph[x].add((y,w))\n            graph[y].add((x,w))\n        \n        min_len = n\n        min_city = 0\n        for i in range(n):\n            reached = dijkstra(graph, i, distanceThreshold)\n            if reached <= min_len:\n                min_len = reached\n                min_city = i\n        return min_city\n        \n", "class Solution:\n    def visitedAllNodes(self, src, graph, n, max_d):\n        visited = [False for i in range(n)]\n        heap = [(0, src)]\n        \n        while heap:\n            d, node  = heapq.heappop(heap)\n            if not visited[node]:\n                visited[node] = True\n                for neighbor,w in graph[node]:\n                    if d+w <= max_d and not visited[neighbor]:\n                        heapq.heappush(heap, (d+w, neighbor))\n                        \n            \n        return sum(visited)\n        \n        \n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        graph = collections.defaultdict(list)\n        node, nodes_reached = -1, n+1\n        for i,j,w in edges:\n            graph[i].append((j,w))\n            graph[j].append((i,w))\n            \n        for i in range(n):\n            count = self.visitedAllNodes(i, graph, n, distanceThreshold)\n            if count <= nodes_reached:\n                node = i\n                nodes_reached = count\n        return node\n            \n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        adjl = [[] for _ in range(n)]\n        d = distanceThreshold\n        for e in edges:\n            i, j, w = e\n            adjl[i].append((w, j))\n            adjl[j].append((w, i))\n        inf = float('inf')\n        minc = 1e9\n        mini = 0\n        for i in range(n):\n            ds = [inf for _ in range(n)]\n            ds[i] = 0\n            fringe = [(e[0], (i, e[1])) for e in adjl[i]]\n            heapq.heapify(fringe)\n            visited = {i}\n            while len(fringe) > 0:\n                w, uv = heapq.heappop(fringe)\n                u, v = uv\n                if w > d:\n                    continue\n                if v not in visited:\n                    ds[v] = min(ds[v], w)\n                    for e in adjl[v]:\n                        heapq.heappush(fringe, (e[0] + ds[v], (v, e[1])))\n                    visited.add(v)\n            cnt = len([c for c in ds if c <= d])\n            if cnt <= minc:\n                minc = cnt\n                mini = i\n        return mini\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \n        distance = [[float(\\\"inf\\\")] * n for i in range(n)]\n        \n        for city_1, city_2, weight in edges:\n            \n            distance[city_1][city_2] = weight\n            distance[city_2][city_1] = weight\n            \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    \n                    if i == j:\n                        continue\n                    \n                    distance[i][j] = min(distance[i][k] + distance[k][j], distance[i][j])\n                    distance[j][i] = distance[i][j]\n                            \n        counts = []\n        for i in range(n):\n            \n            within_threshold = 0\n            for j in range(n):\n                \n                if distance[i][j] <= distanceThreshold:\n                    within_threshold += 1\n                    \n            counts.append(within_threshold)\n                        \n        minimum_city_index = -1\n        minimum_city_distance = float(\\\"inf\\\")\n        for i in range(n):\n            \n            if counts[i] <= minimum_city_distance:\n                \n                minimum_city_index = i\n                minimum_city_distance = counts[i]\n                \n        return minimum_city_index\n            \n            ", "import heapq\nclass Solution:\n  # return number of nodes reachable\n  def shortestPath(self, root, graph, distanceThreshold):\n    \n    # shortest distance to root\n    dist = {}\n    dist[root] = 0\n    visited = set()\n    # [(dist, root)]\n    queue = [(0, root)]\n    count = 0\n    while queue:\n      pickDist, pick = heapq.heappop(queue)\n      if pick in visited:\n        continue\n      visited.add(pick)\n      if pickDist <= distanceThreshold:\n        count += 1\n      else:\n        continue\n      for neighbor, weight in graph[pick]:\n        dist[neighbor] = min(dist.get(neighbor, float('inf')), pickDist + weight)\n        heapq.heappush(queue, (dist[neighbor], neighbor))\n    \n    return count\n    \n  def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n    # node from 0 to n-1\n    # multiple undirected graphs?\n  \n    # construct graph: node -> [(node, weight)]\n    graph = {k: [] for k in range(n)}\n    for u, v, w in edges:\n      graph[u].append((v, w))\n      graph[v].append((u, w))\n    \n    minReachableCount = float('inf')\n    ans = 0\n    # for every node, run dijkastra algorithm, stop when the threshold is reached\n    for i in range(n):\n      reachCount = self.shortestPath(i, graph, distanceThreshold)\n      if reachCount <= minReachableCount:\n        minReachableCount = reachCount\n        ans = i\n        \n    return ans\n", "from collections import defaultdict\nimport heapq\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        results = []\n        graph = defaultdict(dict)\n        for x, y, dist in edges:\n            graph[x][y] = dist\n            graph[y][x] = dist\n        for i in range(n):\n            results.append(self.traverse(graph, distanceThreshold, i, n))\n        min_result = min(results)\n        for i in range(n-1, -1, -1):\n            if results[i] == min_result:\n                return i\n        return \n    \n    def traverse(self, graph, threshold, start, n):\n        q = [[start, 0]]\n        count = 0\n        distances = [float('inf')] * n\n        distances[start] = 0\n        while q:\n            city, dist = heapq.heappop(q)\n            for key in list(graph[city].keys()):\n                new_dist = dist + graph[city][key]\n                if distances[key] > new_dist:\n                    distances[key] = new_dist\n                    heapq.heappush(q, [key, dist + graph[city][key]])\n        count = sum([1 for x in distances if x <= threshold])\n        return count - 1\n                    \n        \n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \n        from heapq import heappush, heappop\n        \n        dis = [[float('inf')]*n for _ in range(n)]\n        nei = collections.defaultdict(list)\n        for i,j,x in edges:\n            dis[i][j] = dis[j][i] = x\n            nei[i].append(j)\n            nei[j].append(i)\n        for i in range(n):\n            dis[i][i] = 0\n        \n        # Dijkstra\n        visited = set()\n        for i in range(n):\n            pool = [(0,i)]                                          # pool[j] = x:  d(i,j) = x    \n            while pool:\n                x,j = heappop(pool)                                 # x = d(i,j)\n                if (i,j) not in visited and x <= distanceThreshold: # early stop, if distance exceeds threshold\n                    visited.add((i,j))\n                    for k in nei[j]:\n                        dis[i][k] = min(dis[i][k], x+dis[j][k])     # dis(i,k) = min(dis(i,k), dis(i,j)+dis(j,k))\n                        heappush(pool, (dis[i][k], k))\n        globalMin = [-1, -1]\n        for i in range(n):\n            total = 0\n            for j in range(n):\n                if dis[i][j] <= distanceThreshold:\n                    total += 1\n            if globalMin[0] == -1 or total <= globalMin[0]:\n                globalMin[0] = total\n                globalMin[1] = i\n        return globalMin[1]\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        dist = [[math.inf] * n for i in range(n)]\n        \n        for e in edges:\n            dist[e[0]][e[1]] = e[2]\n            dist[e[1]][e[0]] = e[2]\n            \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])\n        \n        print(dist)\n        \n        max_city_numbers = n+1\n        selected_city = n\n        for i in range(n-1, -1, -1):\n            city_numbers = 0\n            for j in range(n):\n                if i != j and dist[i][j] <= distanceThreshold:\n                    city_numbers += 1\n            print(city_numbers)\n            if city_numbers < max_city_numbers:\n                max_city_numbers = city_numbers\n                selected_city = i\n                \n        return selected_city", "from heapq import heappush, heappop\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \n        def dijkstra(graph, start, distance):\n            reached = set()\n            heap = [(0, start)]\n            while heap:\n                w, node = heappop(heap)\n                if node in reached:\n                    continue\n                if w > distance:\n                    continue\n                if node != start:\n                    reached.add(node)\n                for nex, nex_w in graph[node]:\n                    heappush(heap, (w + nex_w, nex))\n            return reached\n        \n        graph = collections.defaultdict(set)        \n        for x,y,w in edges:\n            graph[x].add((y,w))\n            graph[y].add((x,w))\n        \n        min_len = n\n        min_city = 0\n        for i in range(n):\n            reached = dijkstra(graph, i, distanceThreshold)\n            if len(reached) <= min_len:\n                min_len = len(reached)\n                min_city = i\n        return min_city\n        \n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        dp = [[float(inf)] * n for _ in range(n)]\n        \n        for a,b, cost in edges:\n            dp[a][b] = cost\n            dp[b][a] = cost\n        \n        for i in range(n):\n            dp[i][i] = 0\n        \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])\n\n        idx = 0\n        m = len([e for e in dp[0] if e <= distanceThreshold])\n        for i in range(1,n):\n            l = len([e for e in dp[i] if e <= distanceThreshold])\n            if l <= m:\n                m = l\n                idx = i\n        return idx\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        graph = [[float('inf') for _ in range(n)] for _ in range(n)]\n        for v1, v2, w in edges:\n            graph[v1][v2] = w\n            graph[v2][v1] = w\n        for i in range(n):\n            graph[i][i] = 0\n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])\n        \n        # print(graph)\n        \n        currmin = float('inf')\n        currv = -1\n        for i in range(n):\n            curr = 0\n            for j in range(n):\n                if graph[i][j] <= distanceThreshold:\n                    curr += 1\n                    if curr > currmin:\n                        break\n            if curr <= currmin:\n                # print(i, curr)\n                currmin = curr\n                currv = i\n        return currv\n                    \n        \n                \n                \n            \n", "\n\n\nfrom heapq import *\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n\n        def find_n_neigh(source_city):\n\n            visited = set()\n            pq = [(0, source_city)]\n\n            while pq:\n\n                trav_dist, curr_city = heappop(pq)\n\n                if curr_city in visited:\n                    continue\n\n                if curr_city != source_city:\n                    visited.add(curr_city)\n\n                for neigh, distance in graph[curr_city]:\n                    if neigh not in visited and trav_dist + distance <= distanceThreshold:\n                        heappush(pq, (trav_dist + distance, neigh))\n\n            return len(visited)\n\n\n        graph = defaultdict(list)\n        for city, neigh, distance in edges:\n            graph[city].append((neigh, distance))\n            graph[neigh].append((city, distance))\n\n        n_neighs = [find_n_neigh(city) for city in range(n)]\n        min_n = min(n_neighs)\n        return [city for city in range(n) if n_neighs[city] == min_n][-1]\n\n\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n\n        graph = defaultdict(list)\n        for u, v, w in edges:\n            graph[u].append((v, w))\n            graph[v].append((u, w))\n         \n        \n        output = []\n        queue = deque([])\n        \n        for i in range(n):\n            \n            queue.append((i, 0))\n            curr = {}\n            \n            while queue:\n                \n                node, dist = queue.popleft()\n                \n                if node in curr and dist >= curr[node]:\n                    continue\n                \n                curr[node] = dist\n                \n                for nei, newDist in graph[node]:\n                    if dist + newDist <= distanceThreshold:\n                        queue.append((nei, dist + newDist))\n                        \n            output.append(len(curr) -1)\n            \n        for node in reversed(range(len(output))):\n            if output[node] == min(output):\n                return node", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        # matrices\n        # for i,j,k\n        # min value\n        matrix = [[float('inf') for x in range(n)] for y in range(n)]\n        \n        # build initial matrix\n        for i in range(n):\n            matrix[i][i] = 0\n                    \n        for u,v,w in edges:\n            matrix[u][v] = w\n            matrix[v][u] = w\n\n        \n        print(matrix)\n\n        \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    matrix[i][j] = min(matrix[i][j], matrix[i][k]+matrix[k][j])\n\n        print(matrix)\n        res = defaultdict(int)\n        for i, row in enumerate(matrix):\n            for j, dist in enumerate(row):\n                if dist <= distanceThreshold and i != j :\n                    res[i] += 1\n        \n        # check if unconnected cities\n        unconnected = []\n        i = 0\n        while i < n:\n            if res[i] == 0:\n                # not conencted\n                unconnected.append(i)\n            i += 1\n                \n        if len(unconnected) == 1:\n            return unconnected[0]\n        elif len(unconnected) > 1:\n            return max(unconnected)\n            \n        \n        ans = min(res.values())\n        max_city = 0\n        \n        for city in range(len(res)):\n            if res[city] <= ans and city > max_city:\n                max_city = city\n                \n        print(res)\n        print(ans)\n        print(max_city)\n        return max_city", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        graph = defaultdict(list)\n        result = {} \n\n        # build the adjacency list\n        for edge in edges:\n            src = edge[0]\n            dest = edge[1]\n            cost = edge[2]\n\n            graph[src].append((dest, cost))\n            graph[dest].append((src, cost))\n\n        # {0: [(1, 3)], 1: [(2, 1), (3, 4)], 2: [(3, 1)]}\n        # get the number of vertices that can be reached starting from vertex i. Also, the vertices\n        # that can be reached should have a distance below the threshold.\n        for i in range(n): # 0\n            num_vertices = self.get_num_vertices_less_than_threshold(graph, i, distanceThreshold) # g, 0, 4\n            result[i] = num_vertices\n        \n        # pprint.pprint(result)\n        min_vertex_val = min(result.values())\n        # pprint.pprint(min_vertex_val)\n\n        index = list([-1 if x[1] != min_vertex_val else x[0] for x in list(result.items())])\n\n        # pprint.pprint(index)\n\n        # min_vertex = sorted(result.items(), key=lambda x: x[1])\n        # pprint.pprint(min_vertex)\n\n        return max(index)\n    \n    def get_num_vertices_less_than_threshold(self, graph, vertex, thresh): # g, 0, 4\n        queue = [] \n        queue.append((0, vertex)) # (0, 0) \n        reachable_nodes = [] # []\n\n        while queue: # (3, 1)\n            dist, node = heapq.heappop(queue) # 3, 1\n\n            if node in reachable_nodes:\n                continue\n            \n            reachable_nodes.append(node) # [0, 1]\n\n            for vert in graph[node]: # (2, 1), (3, 4)\n                neigh_vert = vert[0] # 2\n                neigh_cost = vert[1] # 1\n\n                if dist + neigh_cost <= thresh: # 3 + 1 <= 4\n                    heapq.heappush(queue, (dist + neigh_cost, neigh_vert)) # [(4, 1)]\n\n        return len(reachable_nodes) - 1 \n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        dp = [[sys.maxsize for _ in range(n)] for _ in range(n)] \n        for s, e, w in edges:\n            dp[s][e] = w\n            dp[e][s] = w\n            \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    if dp[i][k]!=sys.maxsize and dp[j][k]!=sys.maxsize:\n                        dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])\n        result = [0 for i in range(n)]\n        for i in range(n):\n            for j in range(i+1, n):\n                if dp[i][j]<=distanceThreshold:\n                    result[i]+=1\n                    result[j]+=1\n        # print(result)        \n        return min([(i, val) for i, val in enumerate(result)], key=lambda x: (x[1], -x[0]))[0]            ", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        dist = [[math.inf] * n for i in range(n)]\n        \n        for e in edges:\n            dist[e[0]][e[1]] = e[2]\n            dist[e[1]][e[0]] = e[2]\n            \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])\n        \n        \n        max_city_numbers = n+1\n        selected_city = n\n        for i in range(n-1, -1, -1):\n            city_numbers = 0\n            for j in range(n):\n                if i != j and dist[i][j] <= distanceThreshold:\n                    city_numbers += 1\n            \n            if city_numbers < max_city_numbers:\n                max_city_numbers = city_numbers\n                selected_city = i\n                \n        return selected_city", "import gc\nfrom collections import defaultdict\ngc.disable()\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        graph = [[math.inf for _ in range(n)] for _ in range(n)]\n        for source, sink, cost in edges:\n            graph[source][sink] = cost\n            graph[sink][source] = cost\n        for k in range(n):\n            for i in range(n):\n                if i == k: continue\n                for j in range(n):\n                    if i == j or j == k: continue\n                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])\n        counts_map = defaultdict(lambda: -1)\n        for i in range(n):\n            count = 0\n            for x in graph[i]:\n                if x <= distanceThreshold: count += 1\n            counts_map[count] = max(counts_map[count], i)\n        return counts_map[min(counts_map.keys())]\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        graph = [[float('inf') for _ in range(n)] for _ in range(n)]\n        for v1, v2, w in edges:\n            graph[v1][v2] = w\n            graph[v2][v1] = w\n        for i in range(n):\n            graph[i][i] = 0\n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])\n        \n        print(graph)\n        \n        currmin = float('inf')\n        currv = -1\n        for i in range(n):\n            curr = 0\n            for j in range(n):\n                if graph[i][j] <= distanceThreshold:\n                    curr += 1\n                    if curr > currmin:\n                        break\n            if curr <= currmin:\n                # print(i, curr)\n                currmin = curr\n                currv = i\n        return currv\n                    \n        \n                \n                \n            \n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        def BFS(queue):\n            while queue:\n                route , wt = queue.popleft()\n                for node , node_wt in d[route]:\n                    if min_wt[node] > node_wt + wt:\n                        queue.append([node , node_wt + wt])\n                        min_wt[node] = node_wt + wt\n            return min_wt\n        d , seen ,ans , m = defaultdict(list) , set()  , [] , inf\n        for x , y , z in edges:d[x] += [[y,z]];d[y] += [[x,z]]\n        for i in range(n):\n            min_wt = [inf]*(n)\n            ans.append(BFS(deque([[i,0]])))\n            min_wt[i] = inf\n        res = 0\n        for q,i in enumerate(ans):\n            count = 0\n            for j in i:\n                if j <= distanceThreshold:count += 1\n            if count <= m :res = q;m = count\n        return res", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        from collections import defaultdict\n        graph = defaultdict(list)\n        for start, finish, distance in edges:\n            graph[start].append([distance, finish])\n            graph[finish].append([distance, start])\n        \n        #start from each node\n        #record all the neighbors that are within the threashold distance from the starting node\n        reachable_within_threashold = {}\n        import heapq\n        \n        for house in range(n):\n            if house not in graph:\n                continue\n                #reachable_within_threashold[house] = []\n            else:\n                heap = [[0, house]]\n                reachable_from_this_house = []\n                while heap:\n                    distance_sofar, cur_house = heapq.heappop(heap)\n                    if distance_sofar > distanceThreshold:\n                        continue\n                    if cur_house in reachable_from_this_house:\n                        continue\n                    if cur_house in graph:\n                        for dis, neighbor in graph[cur_house]:\n                            if neighbor not in reachable_from_this_house:\n                                heapq.heappush(heap, [dis+distance_sofar,neighbor])\n                    if cur_house != house:\n                        reachable_from_this_house.append(cur_house)\n            reachable_within_threashold[house] = reachable_from_this_house\n        \n        #print(reachable_within_threashold)\n        for house in range(n-1, -1, -1):\n            if house not in reachable_within_threashold:\n                return house\n        \n        min_ = float('inf')\n        result = float('inf')\n        for house in range(n-1, -1, -1):\n            cur_no = len(reachable_within_threashold[house])\n            if cur_no < min_:\n                min_ = cur_no\n                result = house\n        return result\n", "class Solution:\n    def findTheCity(self, n, edges, threshold):\n        adj=[[] for _ in range(n)]\n        for u,v,w in edges:\n            adj[u].append((w,v))\n            adj[v].append((w,u))\n\n        ans=0\n        mn=100\n        for x in range(n):\n            cur=0\n            vis={x}\n            dist=[threshold]*n\n            hp=[(0,x)]\n            while hp:\n                d,u=heappop(hp)\n                for w,v in adj[u]:\n                    if d+w<=dist[v]:\n                        dist[v]=d+w\n                        vis.add(v)\n                        heappush(hp,(d+w,v))\n            if len(vis)<=mn:\n                mn=len(vis)\n                ans=x\n        \n        return ans", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \n        dist = [[float('inf')] * n for _ in range(n)]\n        for i in range(n):\n            dist[i][i] = 0\n        for pair in edges:\n            a, b, c = pair\n            dist[a][b] = dist[b][a] = c\n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])\n                        \n        res = {len([x for x in dist[i] if x <= distanceThreshold]) : i for i in range(n)}        \n        return res[min(res)]", "from collections import defaultdict\nfrom collections import deque\n\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        n2n = defaultdict(list)\n        for x, y, w in edges:\n            n2n[x].append([y, w])\n            n2n[y].append([x, w])\n\n        minds = [[-1] * n for _ in range(n)]\n\n        for i in range(n):\n            minds[i][i] = 0\n\n        for x, y, d in edges:\n            minds[x][y] = d\n            minds[y][x] = d\n\n        for source in range(n):\n            visited = [0] * n\n            q = deque()\n            q.append(source)\n            visited[source] = 1\n\n            while q:\n                node = q.popleft()\n                for next_node, d in n2n.get(node, []):\n                    if not visited[next_node]:\n                        q.append(next_node)\n                        visited[next_node] = 1\n                        if minds[source][next_node] == -1 or minds[source][next_node] > minds[source][node] + d:\n                            minds[source][next_node] = minds[source][node] + d\n                    else:\n                        if minds[source][next_node] == -1 or minds[source][next_node] > minds[source][node] + d:\n                            minds[source][next_node] = minds[source][node] + d\n                            q.append(next_node)\n\n\n        min_reach = n\n        max_node = 0\n        for source in range(n):\n            reach_count = 0\n            for mind in minds[source]:\n                if mind != -1 and  mind <= distanceThreshold:\n                    reach_count += 1\n            if reach_count <= min_reach:\n                max_node = source\n                min_reach = reach_count\n\n        return max_node\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \n        from heapq import heappush, heappop\n        \n        dis = [[float('inf')]*n for _ in range(n)]\n        nei = collections.defaultdict(list)\n        for i,j,x in edges:\n            dis[i][j] = dis[j][i] = x\n            nei[i].append(j)\n            nei[j].append(i)\n        for i in range(n):\n            dis[i][i] = 0\n        \n        # Dijkstra\n        visited = set()\n        for i in range(n):\n            pool = [(0,i)]                                          # pool[j] = x:  d(i,j) = x    \n            while pool:\n                x,j = heappop(pool)                                 # x = d(i,j)\n                if (i,j) not in visited and x <= distanceThreshold: # early stop, if distance exceeds threshold\n                    visited.add((i,j))\n                    for k in nei[j]:\n                        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))\n                        heappush(pool, (dis[i][k], k))\n        globalMin = [-1, -1]\n        for i in range(n):\n            total = 0\n            for j in range(n):\n                if dis[i][j] <= distanceThreshold:\n                    total += 1\n            if globalMin[0] == -1 or total <= globalMin[0]:\n                globalMin[0] = total\n                globalMin[1] = i\n        return globalMin[1]\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        graph = [[float('inf')] * n for i in range(n)]\n        for u, v, w in edges:\n            graph[u][v] = graph[v][u] = w\n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    if i == j: graph[i][j] = 0\n                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])\n        minCount, city = float('inf'), -1\n        for i in range(n):\n            count = sum([1 for j in range(n) if j != i and graph[i][j] <= distanceThreshold])\n            if count <= minCount:\n                minCount, city = count, i\n        return city", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], T: int) -> int:\n        dis = collections.defaultdict(lambda: float(\\\"inf\\\"))\n        for i in range(n):\n            dis[i, i] = 0\n        for i, j, w in edges:\n            dis[i, j] = dis[j, i] = w\n            \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    dis[i, j] = min(dis[i, j], dis[i, k]+dis[k, j])\n        count = [0]*n\n        for i in range(n):\n            for j in range(n):\n                if i == j: continue\n                count[i] += dis[i, j] <= T\n        mincount = min(count)\n        return max(i for i, c in enumerate(count) if c == mincount)\n        ", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        INF = float('inf')\n        AdjMat = [[INF] * n for _ in range(n)]\n        \n        for i in range(n):\n            AdjMat[i][i] = 0\n            \n        for u,v,w in edges:\n            AdjMat[u][v] = w\n            AdjMat[v][u] = w\n            \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    AdjMat[i][j] = min(AdjMat[i][j], AdjMat[i][k] + AdjMat[k][j])\n                    \n        d = {}\n        for i in range(n):\n            c = -1\n            for j in range(n):\n                if AdjMat[i][j] <= distanceThreshold:\n                    c += 1\n                    \n            d[i] = c\n            \n        m = min(d.values())\n        res = 0\n        for k in d:\n            if d[k] == m:\n                res = max(res,k)\n                \n        return res\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        from heapq import heappush, heappop\n        \n        dis = [[float('inf')]*n for _ in range(n)]\n        nei = collections.defaultdict(list)\n        for i,j,x in edges:\n            dis[i][j] = dis[j][i] = x\n            nei[i].append(j)\n            nei[j].append(i)\n        for i in range(n):\n            dis[i][i] = 0\n        \n        # Dijkstra\n        visited = set()\n        for i in range(n):\n            pool = [(0,i)]                                          # pool[j] = x:  d(i,j) = x    \n            while pool:\n                x,j = heappop(pool)                                 # x = d(i,j)\n                if (i,j) not in visited and x <= distanceThreshold: # early stop, if distance exceeds threshold\n                    visited.add((i,j))\n                    for k in nei[j]:\n                        dis[i][k] = min(dis[i][k], x+dis[j][k])     # dis(i,k) = min(dis(i,k), dis(i,j)+dis(j,k))\n                        heappush(pool, (dis[i][k], k))\n\n        cities = {sum(d <= distanceThreshold for d in dis[i]):i for i in range(n)}\n        return cities[min(cities)]", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        g = [n * [float(\\\"inf\\\")] for _ in range(n)]\n        \n        for a, b, w in edges:\n            g[a][b] = g[b][a] = w\n            \n        # Floyd-Warshall complexity: O(n**3) \n        \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    g[i][j] = min(g[i][j], g[i][k] + g[k][j])\n        \n        res = -1\n        resum = float(\\\"inf\\\")\n        \n        for i in range(n):\n            \n            isum = 0\n            for j in range(n):\n                if j != i and g[i][j] <= distanceThreshold:\n                    isum += 1\n            \n            if isum <= resum:\n                resum = isum\n                res = i\n        \n        return res", "\n\nclass Solution:\n    def findTheCity(self, n, edges, threshold):\n        adj = [[] for _ in range(n)]\n        for u, v, w in edges:\n            adj[u].append((w, v))\n            adj[v].append((w, u))\n\n        ans = mn = 100\n        for x in range(n):\n            cur = 1\n            vis = {x}\n            dist = [threshold+1] * n\n            hp = [(0, x)]\n            \n            while hp:\n                d, u = heappop(hp)\n                if d > dist[u]:\n                    continue\n                for w, v in adj[u]:\n                    if d+w < dist[v]:\n                        vis.add(v)\n                        dist[v] = d+w\n                        heappush(hp, (d+w, v))\n                        \n            if len(vis) <= mn:\n                mn = len(vis)\n                ans = x\n        \n        return ans", "\n\n\nfrom heapq import *\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n\n        def find_n_neighbours(source_city):\n\n            visited = set()\n            heap = [(0, source_city)]\n\n            while heap:\n                travelled_distance, curr_city = heappop(heap)\n                if curr_city in visited:\n                    continue\n\n                if curr_city != source_city:\n                    visited.add(curr_city)\n\n                for neigh, distance in graph[curr_city]:\n                    if neigh in visited:\n                        continue\n\n                    if travelled_distance + distance <= distanceThreshold:\n                        heappush(heap, (travelled_distance + distance, neigh))\n\n            return len(visited)\n\n        graph = defaultdict(list)        \n        for from_, to, distance in edges:\n            graph[from_].append((to, distance))\n            graph[to].append((from_, distance))\n\n        neighbours = [find_n_neighbours(i) for i in range(n) ]\n        min_count = min(neighbours)\n        sel_cities = [i for i in range(n) if neighbours[i] == min_count]\n        return sel_cities[-1]\n", "class Solution:\n    \n    def bfs(self, graph, src, num_nodes, threshold):\n        \n        d = [float('inf')] * num_nodes\n        q = []\n        \n        q.append(src)\n        d[src] = 0\n        \n        while len(q) > 0:\n            u = q.pop(0)\n            #print('Exploring edges of u = ', u)\n            for v in graph[u]:\n                #print(v)\n                if d[v[0]] > d[u] + v[1]:\n                    d[v[0]] = d[u] + v[1]\n                    q.append(v[0])\n        #print(d)\n        return len([i for i,x in enumerate(d) if x <= threshold and x != 0])\n                    \n                \n        \n        \n    \n    \n    \n    \n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \n        # form a graph\n        \n        graph = collections.defaultdict(list)\n        \n        for e in edges:\n            graph[e[0]].append([e[1], e[2]])\n            graph[e[1]].append([e[0], e[2]])\n        \n        #print(self.bfs(graph, 4, n, distanceThreshold))\n        \n        min_val = float('inf')\n        node = -1\n        for i in range(n):\n            r = self.bfs(graph, i, n, distanceThreshold)\n            if r <= min_val:\n                node = i\n                min_val = r\n                \n        return node\n                \n            \n        \n        \n        \n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n    \n        # make graph\n        dist = [[float('inf')] * n for _ in range(n)]\n        \n        for u, v, w in edges:\n            dist[u][v] = w\n            dist[v][u] = w\n            \n        # use Floyd-Warshall Algorithm to find the minimum dist between any pair of nodes\n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    # in case there is a cycle, keep dist[i][j] as inf\n                    if i == j:\n                        continue\n                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])\n    \n        # for all starting node, find their neihboring cities and return the one having fewest neighbors\n        mn = n + 1\n        output = None\n        for start in range(n):\n            count = len([d for d in dist[start] if d <= distanceThreshold])\n            if count <= mn:\n                mn = count\n                output = start\n        return output", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        oe = {}\n        for l, r, w in edges:       \n            if l not in oe:\n                oe[l] = set()\n            if r not in oe:\n                oe[r] = set()\n            oe[l].add((r, w))\n            oe[r].add((l, w))\n        \n        def dks(been, c, t):\n            cw = been[c]        # Current Weight\n            if c not in oe:     # No route to any other city\n                return\n            pending = set()\n            for other, weight in oe[c]:\n                ow = weight + cw     # From current city to the other city weight\n                if ow > distanceThreshold:\n                    continue\n                \n                if other not in been:\n                    been[other] = ow\n                    pending.add(other)\n                    continue\n                if been[other] > ow: # Through this city is more effcient\n                    been[other] = ow\n                    pending.add(other)\n\n            for o in pending:\n                dks(been, o, t)\n    \n            \n        smallest = 0\n        mc = n+1\n        for city in range(n):\n            dv = {city: 0}\n            dks(dv, city, distanceThreshold)\n            # print(dv)\n            cities = len(list(dv.keys())) - 1\n            if cities <= mc:\n                smallest = city\n                mc = cities\n        return smallest\n        \n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        adj = collections.defaultdict(dict)\n        for a,b,c in edges:\n            adj[a][b] = adj[b][a] = c\n        def bfs(s, distanceThreshold):\n            visited = [False] * n\n            dist = [float('inf')] * n\n            frontier = [(0, s)]\n            \n            while frontier:\n                d, s = heapq.heappop(frontier)\n                if d > distanceThreshold: break\n                dist[s] = d\n                visited[s] = True\n                for t in adj[s]:\n                    if not visited[t]:\n                        heapq.heappush(frontier, (d + adj[s][t], t))\n            return len([d for d in dist if d <= distanceThreshold])\n        res = 0\n        count = n\n        for i in range(n):\n            c = bfs(i, distanceThreshold)\n            if c <= count:\n                res = max(res, i)\n                count = c\n        return res\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        adj = collections.defaultdict(dict)\n        for a,b,c in edges:\n            adj[a][b] = adj[b][a] = c\n        def bfs(s, distanceThreshold):\n            visited = [False] * n\n            dist = [float('inf')] * n\n            frontier = [(0, s)]\n            visited[s] = True\n            dist[s] = 0\n            while frontier:\n                d, s = heapq.heappop(frontier)\n                if d > distanceThreshold: break\n                dist[s] = d\n                visited[s] = True\n                for t in adj[s]:\n                    if not visited[t]:\n                        heapq.heappush(frontier, (d + adj[s][t], t))\n            return len([d for d in dist if d <= distanceThreshold])\n        res = 0\n        count = n\n        for i in range(n):\n            c = bfs(i, distanceThreshold)\n            if c <= count:\n                res = max(res, i)\n                count = c\n        return res\n", "import numpy as np\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        dist=np.inf*np.ones((n,n))\n        for k in range(len(edges)):\n            dist[edges[k][0],edges[k][1]]=edges[k][2]\n            dist[edges[k][1],edges[k][0]]=edges[k][2]\n        for k in range(n):\n            dist[k,k]=0\n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    if dist[i,j]>dist[i,k]+dist[j,k]:\n                        dist[i,j]=dist[i,k]+dist[j,k]\n   \n        dist[dist>distanceThreshold]=0\n        dist[dist>0]=1\n\n        number=np.sum(dist,1)\n     \n        curr_min=n\n        index=0\n        for k in range(n):\n            if number[k]<=curr_min:\n                curr_min=number[k]\n                index=k\n        \n        return index\n        \n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n\n        matrix = [[float('inf') for x in range(n)] for y in range(n)]\n        \n        # populate self loops\n        for i in range(n):\n            matrix[i][i] = 0\n        \n        # populate initial matrix\n        for u,v,w in edges:\n            matrix[u][v] = w\n            matrix[v][u] = w\n\n        # floyd-warshall       \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    matrix[i][j] = min(matrix[i][j], matrix[i][k]+matrix[k][j])                  \n        \n        # get amount of below threshold cities\n        res = defaultdict(int)\n        for i, row in enumerate(matrix):\n            for j, dist in enumerate(row):\n                if dist <= distanceThreshold and i != j :\n                    res[i] += 1\n        \n        # check if unconnected cities\n        unconnected = []\n        i = 0\n        while i < n:\n            if res[i] == 0:\n                # not conencted\n                unconnected.append(i)\n            i += 1\n                \n        if len(unconnected) == 1:\n            return unconnected[0]\n        elif len(unconnected) > 1:\n            return max(unconnected)\n            \n        # all cities are connected with each other, get min value\n        ans = min(res.values())\n        max_city = 0\n        \n        # if multiple cities with same minimum neighbours, select biggest one\n        for city in range(len(res)):\n            if res[city] <= ans and city > max_city:\n                max_city = city\n                \n\n        return max_city", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        #Floyd-Warshall\n        \n        dis = [[float(\\\"inf\\\") for _ in range(n)] for _ in range(n)]\n        \n        for edge in edges:\n            dis[edge[0]][edge[1]] = dis[edge[1]][edge[0]] = edge[2]\n        \n        # note the outer loop index must be k\n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j])\n                    \n        min_reach = float('inf')\n        ans = n\n        for i in range(n):\n            reach = 0\n            for j in range(n):\n                if i != j and dis[i][j] <= distanceThreshold:\n                    reach += 1\n            \n            if reach <= min_reach:\n                ans = i\n                min_reach = reach\n \n        return ans", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        g = collections.defaultdict(dict)\n        for i, j, w in edges:\n            g[i][j] = w\n            g[j][i] = w\n        t = distanceThreshold\n        def dist(u):\n            q = [(0, u)]\n            ret = {}\n            while q:\n                d, v = heapq.heappop(q)\n                if v in ret:\n                    continue\n                ret[v] = d\n                for k in g[v]:\n                    if k not in ret and d + g[v][k] <= t:\n                        heapq.heappush(q, (d + g[v][k], k))\n            return len(ret)\n        ans = None\n        num = n + 1\n        for i in range(n):\n            c = dist(i)\n            if c <= num:\n                num = c\n                ans = i\n        return ans\n                \n            \n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        table = [[float('inf') for j in range(n)] for i in range(n)]\n        for i in range(n):\n            table[i][i] = 0\n            \n        for v, u, w in edges:\n            table[u][v] = w\n            table[v][u] = w\n            \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    table[i][j] = min(table[i][j], table[i][k] + table[k][j])\n                    \n        count = [0] * n\n        for i in range(n):\n            for j in range(n):\n                if table[i][j] <= distanceThreshold:\n                    count[i] += 1\n        \n        #print(count)\n        #print(table)\n        m = min(count)                \n        res = -1\n        for i in range(n):\n            if count[i] == m:\n                res = i\n                \n        return res", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        graph = collections.defaultdict(dict)\n        for u, v, w in edges:\n            graph[u][v] = w\n            graph[v][u] = w\n\n        def dijstra(start, distanceThreshold):\n            heap = [(0, start)]\n            des = []\n            while heap:\n                w, u = heapq.heappop(heap)\n                if u not in d:\n                    d[u] = w\n                    for v in graph[u]:\n                        if graph[u][v]+ d[u] <= distanceThreshold:\n                            heapq.heappush(heap, (graph[u][v]+ d[u], v))\n                            if v not in des and v != start:\n                                des.append(v)\n            return len(des)\n\n        res, count  = 0 , n            \n        for i in range(n):\n            d = {} \n            des = dijstra(i, distanceThreshold)\n            if des <= count:\n                res = max(res, i)\n                count = des\n        return res", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        graph = collections.defaultdict(list)\n        for u, v, w in edges: \n            graph[u].append((v, w))\n            graph[v].append((u, w))\n            \n        for k in graph: \n            graph[k].sort(key = lambda x: x[1])\n        \n            \n        def dijk(i, budget): \n            seen, pq = set(), [(0, i, 0)]\n            while pq: \n                cost, u, steps = heapq.heappop(pq)\n                seen.add(u)\n                for nei, weight in graph[u]: \n                    if nei in seen or cost + weight > budget: \n                        continue\n                    else:\n                        heapq.heappush(pq, (cost + weight, nei, steps + 1))\n                       \n                    \n            return len(seen)\n            \n        min_city, ans = n, None\n        for i in range(n): \n            n_reachable = dijk(i, distanceThreshold)\n            if n_reachable <= min_city: \n                min_city, ans = n_reachable, i\n        return ans\n            \n    # def findTheCity(self, n, edges, maxd):\n    #     dis = [[float('inf')] * n for _ in range(n)]\n    #     for i, j, w in edges:\n    #         dis[i][j] = dis[j][i] = w\n    #     for i in range(n):\n    #         dis[i][i] = 0\n    #     for k in range(n):\n    #         for i in range(n):\n    #             for j in range(n):\n    #                 dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])\n    #     res = {sum(d <= maxd for d in dis[i]): i for i in range(n)}\n    #     return res[min(res)]\n", "class Solution:\n    def findTheCity(self, n, edges, maxd):\n        dis = [[float('inf')] * n for _ in range(n)]\n        for i, j, w in edges:\n            dis[i][j] = dis[j][i] = w\n        for i in range(n):\n            dis[i][i] = 0\n            \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])\n                    \n        temp = [sum(d <= maxd for d in dis[i]) for i in range(n)]\n        return [i for i, x in enumerate(temp) if x == min(temp)][-1]\n", "import heapq\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n            def djikstras(edges, cities, src):\n                matrix = {}\n                for edge in edges:\n                    if edge[0] not in matrix:\n                        matrix[edge[0]] = []\n                    matrix[edge[0]].append((edge[1], edge[2]))\n                    #This line holds good only if the graph is bidirectional\n                    if edge[1] not in matrix:\n                        matrix[edge[1]] = []\n                    matrix[edge[1]].append((edge[0], edge[2]))\n\n                vertices = []\n                visited = []\n                heapq.heappush(vertices, (0, src))\n                while vertices :\n                    vertexDist, vertex = heapq.heappop(vertices)\n                    if vertex in visited:\n                        continue\n                    visited.append(vertex)\n                    if vertexDist <= distanceThreshold:\n                        cities.append(vertex)\n                        if vertex in matrix:\n                            for (v, w) in matrix[vertex]:\n                                newDist = vertexDist + w\n                                heapq.heappush(vertices, (newDist , v))\n                return cities\n            \n            cityList = []\n            finalCityList = []\n            for i in range(n):\n                cities = djikstras(edges, [], i)\n                #print(cities, i)\n                #Removing source city\n                if cities:\n                    heapq.heappush(cityList, (len(cities), i*-1))\n                #print(cityList)\n            \n            return heapq.heappop(cityList)[1]*-1", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        g = collections.defaultdict(list)\n        for f, t, w in edges:\n            g[f].append((t, w))\n            g[t].append((f, w))\n        \n        def bfs(i):\n            q = [(0, i)]\n            visited = {i}\n            while q:\n                w, j = heapq.heappop(q)\n                visited.add(j)\n                for k, w_ in g[j]:\n                    if k not in visited and w + w_ <= distanceThreshold:\n                        heapq.heappush(q, (w + w_, k))\n            return visited\n        \n        return -min([(len(bfs(i)), -i) for i in range(n)])[1]", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        graph = collections.defaultdict(list)\n        for u, v, w in edges: \n            graph[u].append((v, w))\n            graph[v].append((u, w))\n            \n        # for k in graph: \n        #     graph[k].sort(key = lambda x: x[1])\n        \n            \n        def dijk(i, budget): \n            seen, pq = set(), [(0, i, 0)]\n            while pq: \n                cost, u, steps = heapq.heappop(pq)\n                seen.add(u)\n                for nei, weight in graph[u]: \n                    if nei in seen or cost + weight > budget: \n                        continue\n                    else:\n                        heapq.heappush(pq, (cost + weight, nei, steps + 1))\n                       \n                    \n            return len(seen)\n            \n        min_city, ans = n, None\n        for i in range(n): \n            n_reachable = dijk(i, distanceThreshold)\n            if n_reachable <= min_city: \n                min_city, ans = n_reachable, i\n        return ans\n            \n    # def findTheCity(self, n, edges, maxd):\n    #     dis = [[float('inf')] * n for _ in range(n)]\n    #     for i, j, w in edges:\n    #         dis[i][j] = dis[j][i] = w\n    #     for i in range(n):\n    #         dis[i][i] = 0\n    #     for k in range(n):\n    #         for i in range(n):\n    #             for j in range(n):\n    #                 dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])\n    #     res = {sum(d <= maxd for d in dis[i]): i for i in range(n)}\n    #     return res[min(res)]\n", "from collections import defaultdict\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        graph = [[math.inf for _ in range(n)] for _ in range(n)]\n        for source, sink, cost in edges:\n            graph[source][sink] = cost\n            graph[sink][source] = cost\n        for k in range(n):\n            for i in range(n):\n                if i == k: continue\n                for j in range(n):\n                    if i == j or j == k: continue\n                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])\n        counts_map = defaultdict(lambda: -1)\n        for i in range(n):\n            count = len([x for x in graph[i] if x <= distanceThreshold])\n            counts_map[count] = max(counts_map[count], i)\n        return counts_map[min(counts_map.keys())]\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        # Floyd Washall\n        # dp[i][j] \u8868\u793a uv \u4e4b\u95f4\u7684\u6700\u5c0f\u8ddd\u79bb\n        dp = [ n * [float('inf')] for _ in range(n)]\n        \n        for f, t, w in edges:\n            dp[f][t] = dp[t][f] = w\n            \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    dp[i][j] = min(dp[i][k] + dp[k][j], dp[i][j])\n                    \n        res = -1\n        minv = float('inf')\n        for i in range(n):\n            count = 0\n            for j in range(n):\n                if i != j and dp[i][j] <= distanceThreshold:\n                    count += 1\n            if count <= minv:\n                minv = count\n                res = i\n        return res\n        \n        \n\n                    \n                    \n            \n                    \n            \n            \n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        g = collections.defaultdict(list)\n        \n        for i , j , w in edges:\n            g[i].append((j,w))\n            g[j].append((i,w))\n            \n        def neighbours(i):    \n            heap = [(0,i)]\n            d = {} # keeps the track of visited array \n\n            while heap:\n                distance , node = heappop(heap)\n                if node in d:  # adding to the visited array \n                    continue\n                if node != i:\n                    d[node] = distance\n\n                for nei,w in g[node]:\n                    if nei in d:\n                        continue\n                    if distance+w <= distanceThreshold:\n                        heappush(heap,(distance+w,nei))\n            return len(d)\n                \n        \n        return max([(neighbours(city), city) for city in range(n)], key=lambda x: (-x[0], x[1]))[-1]\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        graph = collections.defaultdict(set)\n        for u, v, w in edges: \n            graph[u].add((v, w))\n            graph[v].add((u, w))\n            \n        def dijk(i, budget): \n            seen, pq = set(), [(0, i, 0)]\n            while pq: \n                cost, u, steps = heapq.heappop(pq)\n                seen.add(u)\n                for nei, weight in graph[u]: \n                    if nei in seen or cost + weight > budget: \n                        continue\n                    heapq.heappush(pq, (cost + weight, nei, steps + 1))\n            return len(seen)\n            \n        min_city, ans = n, None\n        for i in range(n): \n            n_reachable = dijk(i, distanceThreshold)\n            if n_reachable <= min_city: \n                min_city, ans = n_reachable, i\n        return ans\n            \n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        graph = collections.defaultdict(set)\n        for u, v, w in edges: \n            graph[u].add((v, w))\n            graph[v].add((u, w))\n            \n        def dijk(i, budget): \n            seen, pq = set(), [(0, i, 0)]\n            while pq: \n                cost, u, steps = heapq.heappop(pq)\n                seen.add(u)\n                for nei, weight in graph[u]: \n                    if nei in seen or cost + weight > budget: \n                        continue\n                    heapq.heappush(pq, (cost + weight, nei, steps + 1))\n            return len(seen)\n            \n        min_city, ans = n, None\n        for i in range(n): \n            n_reachable = dijk(i, distanceThreshold)\n            if n_reachable <= min_city: \n                min_city, ans = n_reachable, i\n        return ans\n            \n    # def findTheCity(self, n, edges, maxd):\n    #     dis = [[float('inf')] * n for _ in range(n)]\n    #     for i, j, w in edges:\n    #         dis[i][j] = dis[j][i] = w\n    #     for i in range(n):\n    #         dis[i][i] = 0\n    #     for k in range(n):\n    #         for i in range(n):\n    #             for j in range(n):\n    #                 dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])\n    #     res = {sum(d <= maxd for d in dis[i]): i for i in range(n)}\n    #     return res[min(res)]\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        weight = collections.defaultdict(dict)\n        for u, v, w in edges:\n            weight[u][v] = w\n            weight[v][u] = w\n        \n        def getNumberOfNeighbors(city):\n            heap = [(0, city)]\n            dist = {}\n            \n            while heap:\n                w, u = heapq.heappop(heap)\n                if u not in dist and u != city:\n                    dist[u] = w\n                for v in weight[u]:\n                    if v in dist:\n                        continue\n                    if w + weight[u][v] <= distanceThreshold:\n                        heapq.heappush(heap, (w+weight[u][v], v))\n            return len(dist)\n        minCount = float('inf')\n        ans = None\n        for i in range(n):\n            count = getNumberOfNeighbors(i)\n            if count <= minCount:\n                ans = i\n                minCount = count\n        return ans\n        \n", "import numpy as np\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        A = np.zeros([n, n])    \n        for e in edges:\n            A[e[0]][e[1]] = e[2]\n            A[e[1]][e[0]] = e[2]\n        for i in range(n):\n            for j in range(n):\n                if i == j:\n                    continue\n                if A[i][j] == 0:\n                    A[i][j] = np.inf\n        for k in range(n):\n            for i in range(n):\n                if (i == k):\n                    continue \n                for j in range(n):\n                    if (j == k):\n                        continue\n                    A[i, j] = min(A[i, j], A[i, k] + A[k, j])\n        #print(A)\n        count = np.sum(A <= distanceThreshold, axis=0)\n        minn = count[0]\n        #print(count)\n        argminn = 0\n        for i, c in enumerate(count):\n            if c <= minn:\n                minn = c\n                argminn = i\n        return argminn\n", "import sys\nclass Solution:\n    \n    def constructGraph(self, edges, n):\n        graph = [[sys.maxsize for i in range(n)] for j in range(n)]\n        for i, j, k in edges:\n            graph[i][j] = k\n            graph[j][i] = k\n        return graph\n    \n    def floydWarshall(self, graph, n):\n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    if i == j:\n                        graph[i][j] = 0\n                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])\n                    graph[j][i] = graph[i][j]\n    \n    def getCitiesUnderThreshold(self, graph, distanceThreshold, n):\n        arr = [None for i in range(n)]\n        for i in range(n):\n            lis = []\n            for j in range(n):\n                if graph[i][j] <= distanceThreshold and graph[i][j] != 0:\n                    lis.append(j)\n            arr[i] = lis\n        return arr\n    \n    def cityWithLeastNumber(self, arr):\n        minNum = sys.maxsize\n        for i, j in enumerate(arr):\n            if len(j) <= minNum:\n                minNum = len(j)\n                curr = i\n        return curr\n    \n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        graph = self.constructGraph(edges, n)\n        self.floydWarshall(graph, n)\n        arr = self.getCitiesUnderThreshold(graph, distanceThreshold, n)\n        curr = self.cityWithLeastNumber(arr)\n        return curr", "import heapq\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \n            def djikstras(matrix, cities, src):\n                vertices = []\n                visited = []\n                heapq.heappush(vertices, (0, src))\n                while vertices :\n                    vertexDist, vertex = heapq.heappop(vertices)\n                    if vertex in visited:\n                        continue\n                    visited.append(vertex)\n                    if vertexDist <= distanceThreshold:\n                        cities.append(vertex)\n                        if vertex in matrix:\n                            for (v, w) in matrix[vertex]:\n                                newDist = vertexDist + w\n                                heapq.heappush(vertices, (newDist , v))\n                return cities\n            \n            matrix = {}\n            for edge in edges:\n                if edge[0] not in matrix:\n                    matrix[edge[0]] = []\n                matrix[edge[0]].append((edge[1], edge[2]))\n                #This line holds good only if the graph is bidirectional\n                if edge[1] not in matrix:\n                    matrix[edge[1]] = []\n                matrix[edge[1]].append((edge[0], edge[2]))\n            cityList = []\n            for i in range(n):\n                cities = []\n                if i in matrix:\n                    cities = djikstras(matrix, [], i)\n                else:\n                    cities.append(i)\n                heapq.heappush(cityList, (len(cities), i*-1))\n            #print(cityList)\n            return heapq.heappop(cityList)[1]*-1", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \n        \n        \n        city=0\n        value=float(\\\"inf\\\")\n        graph=defaultdict(list)\n        for i,j,c in edges:\n            graph[i].append([j,c])\n            graph[j].append([i,c])\n        \n        def heap(start):\n            visited=set()\n            minheap=[(0,start)]\n            while minheap:\n                cost,node=heapq.heappop(minheap)\n                if cost<=distanceThreshold:\n                    visited.add(node)\n                else:\n                    continue\n                for i,j in graph[node]:\n                    if i not in visited:\n                        heapq.heappush(minheap,(j+cost,i))\n            return len(visited)-1\n        for i in range(n):\n            ans=heap(i)\n            if ans<=value:\n                value=ans\n                city=i\n        return city\n        ", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        L = [[[float('inf') for i in range(n+1)] for j in range(n)] for k in range(n)]\n\n        for u,v,w in edges:\n            L[u][v][0] = w\n            L[v][u][0] = w\n        \n\n        for k in range(1,n+1):\n            for i in range(n):\n                for j in range(n):\n                    if(j==i):\n                        continue\n                    L[i][j][k] = min(L[i][j][k-1], L[i][k-1][k-1]+L[k-1][j][k-1])\n\n        min_ct = float('inf')\n        minval = n-1\n\n        for i in range(n-1,-1,-1):\n            ct = 0\n            for j in range(n):\n                if(i==j):\n                    continue\n                if(L[i][j][n]<=distanceThreshold):\n                    ct += 1\n            if(ct<min_ct):\n                min_ct = ct\n                minval = i\n        return minval\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        map = collections.defaultdict(set)\n        for f, t, w in edges:\n            map[f].add((t, w))\n            map[t].add((f, w))\n        stack = []\n        empty = -float(\\\"inf\\\")\n        res = 0\n        seen = []\n        for i in range(n):\n            seen.append(collections.defaultdict(int))\n            stack.append((i, i, 0))\n            if i not in map:\n                empty = i\n        if empty != -float(\\\"inf\\\"):\n            return empty\n        while stack:\n            f, t, w = stack.pop()\n            for a, b in map[t]:\n                if a not in seen[f] and w + b <= distanceThreshold and a != f:\n                    seen[f][a] = w + b\n                    stack.append((f, a, w + b))\n                elif a in seen[f] and w + b <= seen[f][a] and a != f:\n                    seen[f][a] = w + b\n                    stack.append((f, a, w + b))\n        l = float(\\\"inf\\\")\n        for k in range(len(seen)):\n            if len(seen[k]) <= l:\n                l = len(seen[k])\n                res = k\n        return res", "import heapq\nfrom collections import defaultdict\nclass Solution:\n    def findTheCity(self, n: int, edges, distanceThreshold: int) -> int:\n        matrix = [[float('inf')]*n for _ in range(n)]\n        graph = defaultdict(list)\n        for s, e, d in edges:\n            matrix[s][e] = d\n            matrix[e][s] = d\n            graph[s].append(e)\n            graph[e].append(s)\n        # print(graph)\n        # print(matrix)\n\n        def dijkstra(source):\n            dist = [float('inf')]*n\n            dist[source] = 0\n            pq = [(0, source)]\n            heapq.heapify(pq)\n            while pq:\n                # print(pq)\n                d, node = heapq.heappop(pq)\n                if d > dist[node]:\n                    continue\n                for next_node in graph[node]:\n                    tmp = d + matrix[node][next_node]\n                    if tmp < dist[next_node]:\n                        dist[next_node] = tmp\n                        heapq.heappush(pq, (tmp, next_node))\n            # print(source, dist)\n            return sum(d <= distanceThreshold for d in dist) - 1\n\n        res, counts = 0, n\n        for i in range(n):\n            tmp = dijkstra(i)\n            # print(tmp, i)\n            if tmp <= counts:\n                counts = tmp\n                res = i\n        return res\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \n        import collections\n        '''\n        graph = collections.defaultdict(list)\n        \n        for edge in edges:\n            graph[edge[0]].append([edge[1]], edge[2])\n        \n        res = []\n        \n        for i in range(n):\n        '''\n        \n        \n        graph = collections.defaultdict(list)\n        \n        for u, v, w in edges:\n            graph[u].append((v, w))\n            graph[v].append((u, w))\n        \n        print([(self.getNumberOfNeighbors(city, graph, distanceThreshold), city) for city in range(n)]) # [(2, 0), (3, 1), (3, 2), (2, 3)] -> len(dist), city\n        print(max([(self.getNumberOfNeighbors(city, graph, distanceThreshold), city) for city in range(n)])) # (3, 2)\n        print(max([(self.getNumberOfNeighbors(city, graph, distanceThreshold), city) for city in range(n)], key=lambda x: (-x[0], x[1]))) # (2, 3)\n        \n        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\n    \n    \n    def getNumberOfNeighbors(self, city, graph, distanceThreshold):\n        heap = [(0, city)]\n        dist = {}\n\n        while heap:\n            currW, visitedCity = heapq.heappop(heap)\n            if visitedCity in dist:\n                continue\n            if city != visitedCity:    \n                dist[visitedCity] = currW\n            for neighborCity, w in graph[visitedCity]:\n                if neighborCity in dist:\n                    continue\n                if currW + w <= distanceThreshold:\n                    heapq.heappush(heap, (currW + w, neighborCity))\n        return len(dist)", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \n        import collections\n        '''\n        graph = collections.defaultdict(list)\n        \n        for edge in edges:\n            graph[edge[0]].append([edge[1]], edge[2])\n        \n        res = []\n        \n        for i in range(n):\n        '''\n        \n        \n        graph = collections.defaultdict(list)\n        \n        for u, v, w in edges:\n            graph[u].append((v, w))\n            graph[v].append((u, w))\n        \n        print([(self.getNumberOfNeighbors(city, graph, distanceThreshold), city) for city in range(n)]) # [(2, 0), (3, 1), (3, 2), (2, 3)] -> len(dist), city\n        print(max([(self.getNumberOfNeighbors(city, graph, distanceThreshold), city) for city in range(n)])) # (3, 2)\n        print(max([(self.getNumberOfNeighbors(city, graph, distanceThreshold), city) for city in range(n)], key=lambda x: (-x[0], x[1]))) # (2, 3)\n        \n        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\n    \n    \n    def getNumberOfNeighbors(self, city, graph, distanceThreshold):\n        heap = [(0, city)]\n        dist = {}\n\n        while heap:\n            currW, u = heapq.heappop(heap)\n            if u in dist:\n                continue\n            if u != city:    \n                dist[u] = currW\n            for v, w in graph[u]:\n                if v in dist:\n                    continue\n                if currW + w <= distanceThreshold:\n                    heapq.heappush(heap, (currW + w, v))\n        return len(dist)", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        map = collections.defaultdict(list)\n        for f, t, w in edges:\n            map[f].append((t, w))\n            map[t].append((f, w))\n        stack = []\n        empty = -float(\\\"inf\\\")\n        res = 0\n        seen = []\n        for i in range(n):\n            seen.append(collections.defaultdict(int))\n            stack.append((i, i, 0))\n            if i not in map:\n                empty = i\n        if empty != -float(\\\"inf\\\"):\n            return empty\n        while stack:\n            f, t, w = stack.pop()\n            for a, b in map[t]:\n                if a not in seen[f] and w + b <= distanceThreshold and a != f:\n                    seen[f][a] = w + b\n                    stack.append((f, a, w + b))\n                elif a in seen[f] and w + b <= seen[f][a] and a != f:\n                    seen[f][a] = w + b\n                    stack.append((f, a, w + b))\n        l = float(\\\"inf\\\")\n        for k in range(len(seen)):\n            if len(seen[k]) <= l:\n                l = len(seen[k])\n                res = k\n        return res", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \n        graph = defaultdict(list)\n        output = []\n        \n        for u, v, w in edges:\n            graph[u].append((v, w))\n            graph[v].append((u, w))\n        \n        for i in range(n):\n            \n            #distance , node\n            queue = [(i, 0)]\n            curr = {}\n            \n            while queue:\n                node, dist = heapq.heappop(queue)\n                \n                if node in curr and dist >= curr[node]:\n                    continue\n                \n                curr[node] = dist\n                \n                for nei, newDist in graph[node]:\n                    if newDist + dist <= distanceThreshold:\n                        heapq.heappush(queue,(nei, newDist + dist))\n            \n            output.append(len(curr)-1)\n        \n        for node in reversed(range(len(output))):\n            if output[node] == min(output):\n                return node", "import heapq\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \n            def djikstras(matrix, cities, src):\n                vertices = []\n                visited = []\n                heapq.heappush(vertices, (0, src))\n                while vertices :\n                    vertexDist, vertex = heapq.heappop(vertices)\n                    if vertex in visited:\n                        continue\n                    visited.append(vertex)\n                    if vertexDist <= distanceThreshold:\n                        cities.append(vertex)\n                        if vertex in matrix:\n                            for (v, w) in matrix[vertex]:\n                                newDist = vertexDist + w\n                                heapq.heappush(vertices, (newDist , v))\n                return cities\n            \n            cityList = []\n            finalCityList = []\n            matrix = {}\n            for edge in edges:\n                if edge[0] not in matrix:\n                    matrix[edge[0]] = []\n                matrix[edge[0]].append((edge[1], edge[2]))\n                #This line holds good only if the graph is bidirectional\n                if edge[1] not in matrix:\n                    matrix[edge[1]] = []\n                matrix[edge[1]].append((edge[0], edge[2]))\n            for i in range(n):\n                cities = djikstras(matrix, [], i)\n                #print(cities, i)\n                #Removing source city\n                if cities:\n                    heapq.heappush(cityList, (len(cities), i*-1))\n                #print(cityList)\n            \n            return heapq.heappop(cityList)[1]*-1", "class Solution:\n    import heapq\n    import collections\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n\n        min_node = -1\n        min_val = float(\\\"inf\\\")\n\n        graph = collections.defaultdict(list)\n        for s, e, d in edges:\n            graph[s].append((e, d))\n            graph[e].append((s, d))\n\n        for node in range(n):\n            pq = [(0, node)]\n            seen = set([node])\n\n            while pq:\n                td, name = heapq.heappop(pq)\n                seen.add(name)\n                for nex, do in graph[name]:\n                    if do + td <= distanceThreshold and nex not in seen:\n                        heapq.heappush(pq, (do + td, nex))\n\n            count = len(seen)\n\n            if count <= min_val:\n                min_node = node\n                min_val = count\n\n        return min_node\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        g = {}\n        for u, v, w in edges:\n            if u in g:\n                g[u].append((v, w))\n            else:\n                g[u] = [(v, w)]\n            if v in g:\n                g[v].append((u, w))\n            else:\n                g[v] = [(u, w)]\n        def numOfNb(city):\n            minheap = [(0, city)]\n            dist = {}\n            while minheap:\n                currw, u = heapq.heappop(minheap)\n                if u != city:\n                    dist[u] = currw\n                if u not in g:\n                    continue\n                for v, w in g[u]:\n                    if v in dist:\n                        continue\n                    if currw + w <= distanceThreshold:\n                        heapq.heappush(minheap, (currw + w, v))\n            return len(dist)\n        ans = 0\n        minnb = n\n        for i in range(n):\n            nb = numOfNb(i)\n            if nb <= minnb:\n                minnb = nb\n                ans = i\n        return ans", "class Solution:\n    import heapq\n    import collections\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n\n        min_node = -1\n        min_val = float(\\\"inf\\\")\n\n        graph = collections.defaultdict(list)\n        for s, e, d in edges:\n            graph[s].append((e, d))\n            graph[e].append((s, d))\n\n        for node in range(n):\n            pq = [(0, node)]\n            seen = set()\n            seen.add(node)\n\n            while pq:\n                td, name = heapq.heappop(pq)\n                seen.add(name)\n                for nex, do in graph[name]:\n                    if do + td <= distanceThreshold and nex not in seen:\n                        heapq.heappush(pq, (do + td, nex))\n\n            count = len(seen)\n\n            if count <= min_val:\n                min_node = node\n                min_val = count\n\n        return min_node\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        g = {}\n        for u, v, w in edges:\n            if u in g:\n                g[u].append((v, w))\n            else:\n                g[u] = [(v, w)]\n            if v in g:\n                g[v].append((u, w))\n            else:\n                g[v] = [(u, w)]\n        def numOfNb(city):\n            minheap = [(0, city)]\n            dist = {}\n            while minheap:\n                currw, u = heapq.heappop(minheap)\n                if u != city:\n                    dist[u] = currw\n                if u not in g or currw > distanceThreshold:\n                    continue\n                for v, w in g[u]:\n                    if v in dist:\n                        continue\n                    if currw + w <= distanceThreshold:\n                        heapq.heappush(minheap, (currw + w, v))\n            return len(dist)\n        ans = 0\n        minnb = n\n        for i in range(n):\n            nb = numOfNb(i)\n            if nb <= minnb:\n                minnb = nb\n                ans = i\n        return ans", "from heapq import *\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \n        \n        g = collections.defaultdict(list)\n        \n        for i , j , w in edges:\n            g[i].append((j,w))\n            g[j].append((i,w))\n            \n        def neighbours(i):    \n            \n            heap = [(0,i)]\n            d = {}\n\n            while heap:\n\n                distance , node = heappop(heap)\n\n                if node in d:\n                    continue\n\n                if node != i:\n                    d[node] = distance\n\n                for nei,w in g[node]:\n                    \n                    if nei in d:\n                        continue\n\n                    if distance+w <= distanceThreshold:\n                        heappush(heap,(distance+w,nei))\n                \n            return len(d)\n                \n        \n        return max([(neighbours(city), city) for city in range(n)], key=lambda x: (-x[0], x[1]))[-1]", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n                        \n        g = collections.defaultdict(list)\n        for u, v, w in edges:\n            g[u].append((v, w))\n            g[v].append((u, w))\n            \n        def dkstr(n):\n            q = [(0, n)]\n            visited = set()\n            while q:\n                dis, node = heapq.heappop(q)\n                visited.add(node)\n                for adj, w in g[node]:\n                    if dis+w <= distanceThreshold and adj not in visited:\n                        heapq.heappush(q, (dis+w, adj))\n        \n            return len(visited) - 1\n        \n        num_city = float(\\\"inf\\\")\n        ans = 0\n        for i in range(n):\n            num_local = dkstr(i)\n            if num_local <= num_city:\n                num_city = num_local\n                ans = i\n\n        return ans\n        ", "class Solution:\n\\tdef findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n\\t\\tmap = collections.defaultdict(set)\n\\t\\tfor f, t, w in edges:\n\\t\\t\\tmap[f].add((t, w))\n\\t\\t\\tmap[t].add((f, w))\n\\t\\tstack = []\n\\t\\tempty = -float(\\\"inf\\\")\n\\t\\tres = 0\n\\t\\tseen = []\n\\t\\tfor i in range(n):\n\\t\\t\\tseen.append(collections.defaultdict(int))\n\\t\\t\\tstack.append((i, i, 0))\n\\t\\t\\tif i not in map:\n\\t\\t\\t\\tempty = i\n\\t\\tif empty != -float(\\\"inf\\\"):\n\\t\\t\\treturn empty\n\\t\\twhile stack:\n\\t\\t\\tf, t, w = stack.pop()\n\\t\\t\\tfor a, b in map[t]:\n\\t\\t\\t\\tif a not in seen[f] and w + b <= distanceThreshold and a != f:\n\\t\\t\\t\\t\\tseen[f][a] = w + b\n\\t\\t\\t\\t\\tstack.append((f, a, w + b))\n\\t\\t\\t\\telif a in seen[f] and w + b <= seen[f][a] and a != f:\n\\t\\t\\t\\t\\tseen[f][a] = w + b\n\\t\\t\\t\\t\\tstack.append((f, a, w + b))\n\\t\\tl = float(\\\"inf\\\")\n\\t\\tfor k in range(len(seen)):\n\\t\\t\\tif len(seen[k]) <= l:\n\\t\\t\\t\\tl = len(seen[k])\n\\t\\t\\t\\tres = k\n\\t\\treturn res", "import heapq\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \n            def djikstras(edges, cities, src):\n                vertices = []\n                visited = []\n                heapq.heappush(vertices, (0, src))\n                while vertices :\n                    vertexDist, vertex = heapq.heappop(vertices)\n                    if vertex in visited:\n                        continue\n                    visited.append(vertex)\n                    if vertexDist <= distanceThreshold:\n                        cities.append(vertex)\n                        if vertex in matrix:\n                            for (v, w) in matrix[vertex]:\n                                newDist = vertexDist + w\n                                heapq.heappush(vertices, (newDist , v))\n                return cities\n            \n            cityList = []\n            finalCityList = []\n            matrix = {}\n            for edge in edges:\n                if edge[0] not in matrix:\n                    matrix[edge[0]] = []\n                matrix[edge[0]].append((edge[1], edge[2]))\n                #This line holds good only if the graph is bidirectional\n                if edge[1] not in matrix:\n                    matrix[edge[1]] = []\n                matrix[edge[1]].append((edge[0], edge[2]))\n            for i in range(n):\n                cities = djikstras(edges, [], i)\n                #print(cities, i)\n                #Removing source city\n                if cities:\n                    heapq.heappush(cityList, (len(cities), i*-1))\n                #print(cityList)\n            \n            return heapq.heappop(cityList)[1]*-1", "from collections import defaultdict\nclass Solution:\n    \n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        dist = defaultdict(list)\n        for x, y, w in edges:\n            dist[x].append((y, w))\n            dist[y].append((x, w))\n        \n        curmin_idx, curmin_val = None, None \n        def dfs(idx, visited, threshold):\n            if threshold < 0: return\n            visited[idx] = threshold \n            \n            for iidx, weight in dist[idx]:\n                if (threshold - weight) > visited[iidx]:\n                    dfs(iidx, visited, threshold - weight)\n                    \n        for i in range(n):\n            visited = [-1] * n\n            dfs(i, visited, distanceThreshold)\n            cur_visited = sum(1 for v in visited if v >= 0)\n            if curmin_val is None or cur_visited <= curmin_val:\n                curmin_val = cur_visited\n                curmin_idx = i\n                          \n             \n        return curmin_idx\n        \n            \n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], d: int) -> int:\n        if n==2:\n            return 1\n        \n        graph = {x:[] for x in range(n)}\n        for edge in edges:\n            graph[edge[0]].append((edge[1],edge[2]))\n            graph[edge[1]].append((edge[0],edge[2]))\n        \n        \n        def reachable(node, visited, threshold, dist):\n            for nei in graph[node]:\n                if dist+nei[1]<visited[nei[0]] and dist+nei[1]<=threshold:\n                    visited[nei[0]] = dist+nei[1] \n                    reachable(nei[0], visited, threshold, dist+nei[1])\n                    \n        res = 0\n        temp = n\n        for i in reversed(list(range(n))):\n            visited = [float('inf') for _ in range(n)]\n            visited[i] = 0\n            c = 0\n            dist = 0\n            for nei in graph[i]:\n                if dist+nei[1]<visited[nei[0]] and dist+nei[1]<=d:\n                    visited[nei[0]] = dist+nei[1] \n                    reachable(nei[0], visited, d,dist+nei[1])\n            \n            for val in visited:\n                if val>0 and val!=float('inf'):\n                    c+=1\n        \n            # print(c,i)\n            if c < temp :\n                res = i\n                temp = c\n        return res\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        adj = [[] for i in range(n)]\n        res = [0 for i in range(n)]\n        ans = float('inf')\n        city = -1\n        \n        # create adj list\n        for i in edges:\n            a, b, c = i\n            adj[a].append((b, c))\n            adj[b].append((a, c))        \n        \n        for i in range(n):\n            visited = [float('inf') for j in range(n)]\n            visited[i] = 0\n            \n            traverse(i, visited, distanceThreshold, 0, adj)\n            \n            res[i] = n - visited.count(float('inf'))  \n            \n        for i in range(n):\n            if res[i] <= ans:\n                ans = res[i]\n                city = i\n            \n        return city\n    \ndef traverse(curr, visited, threshold, dist, adj):\n    \n    if dist > threshold:\n        return\n    \n    visited[curr] = dist\n    \n    for pair in adj[curr]:\n        city, next_dist = pair\n        if dist + next_dist <= visited[city]:\n            traverse(city, visited, threshold, dist + next_dist, adj)", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], d: int) -> int:\n        if n==2:\n            return 1\n        \n        graph = {x:[] for x in range(n)}\n        for edge in edges:\n            graph[edge[0]].append((edge[1],edge[2]))\n            graph[edge[1]].append((edge[0],edge[2]))\n        \n        \n        def reachable(node, visited, threshold, dist):\n            for nei in graph[node]:\n                if dist+nei[1]<visited[nei[0]] and dist+nei[1]<=threshold:\n                    visited[nei[0]] = dist+nei[1] \n                    reachable(nei[0], visited, threshold, dist+nei[1])\n                    \n        res = 0\n        temp = n\n        for i in reversed(list(range(n))):\n            visited = [float('inf') for _ in range(n)]\n            visited[i] = 0\n            c = 0\n            dist = 0\n            for nei in graph[i]:\n                if dist+nei[1]<visited[nei[0]] and dist+nei[1]<=d:\n                    visited[nei[0]] = dist+nei[1] \n                    reachable(nei[0], visited, d,dist+nei[1])\n            \n            for val in visited:\n                if val>0 and val!=float('inf'):\n                    c+=1\n        \n            print((c,i))\n            if c < temp :\n                res = i\n                temp = c\n        return res\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        MAX_VAL = 1e6 + 1\n        self.graph = [[MAX_VAL for _ in range(n)] for _ in range(n)]\n        for idx in range(n): self.graph[idx][idx] = 0\n        for edge in edges:\n            self.graph[edge[0]][edge[1]] = edge[2]\n            self.graph[edge[1]][edge[0]] = edge[2]\n        for k in range(n):\n            for i in range(n):\n                for j in range(i + 1, n):\n                    if self.graph[i][k] + self.graph[k][j] < self.graph[i][j]:\n                        self.graph[i][j] = self.graph[i][k] + self.graph[k][j]\n                        self.graph[j][i] = self.graph[i][k] + self.graph[k][j]\n        results = []\n        for idx in range(n):\n            results.append((idx, len([_ for _ in range(n) if self.graph[idx][_] <= distanceThreshold])))\n        return sorted(results, key=lambda x: (x[1], -x[0]))[0][0]", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \n        if n == 0:\n            return 0\n        \n        if len(edges) == 0:\n            return 0\n        \n        dict1 = collections.defaultdict(list)\n        dict2 = collections.defaultdict(list)\n        for edge in edges:\n            dict1[edge[0]].append((edge[1],edge[2]))\n            dict1[edge[1]].append((edge[0],edge[2]))\n    \n        self.dict1 = dict1\n        self.distanceThreshold = distanceThreshold\n        tempres = []\n        for i in range(n):\n            temp = self.neighbours(i)\n            tempres.append((temp,i))\n        print(tempres)\n        return sorted(tempres, key = lambda x:([x[0]],[-x[1]]))[0][1] \n    \n    def neighbours(self,i):    \n            \n            heap = [(0,i)]\n            d = {}\n\n            while heap:\n\n                distance , node = heappop(heap)\n\n                if node in d:\n                    continue\n\n                if node != i:\n                    d[node] = distance\n\n                for nei,w in self.dict1[node]:\n                    \n                    if nei in d:\n                        continue\n\n                    if distance+w <= self.distanceThreshold:\n                        heappush(heap,(distance+w,nei))\n                \n            return len(d)\n        \n        \n        \n        \n        \n        \n                             \n        \n            \n        \n        \n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \n        import collections\n        '''\n        graph = collections.defaultdict(list)\n        \n        for edge in edges:\n            graph[edge[0]].append([edge[1]], edge[2])\n        \n        res = []\n        \n        for i in range(n):\n        '''\n        \n        \n        graph = collections.defaultdict(list)\n        \n        for u, v, w in edges:\n            graph[u].append((v, w))\n            graph[v].append((u, w))\n            \n        return max([(self.getNumberOfNeighbors(city, graph, distanceThreshold), city) for city in range(n)], key=lambda x: (-x[0], x[1]))[-1]\n    \n    \n    def getNumberOfNeighbors(self, city, graph, distanceThreshold):\n        heap = [(0, city)]\n        dist = {}\n\n        while heap:\n            currW, u = heapq.heappop(heap)\n            if u in dist:\n                continue\n            if u != city:    \n                dist[u] = currW\n            for v, w in graph[u]:\n                if v in dist:\n                    continue\n                if currW + w <= distanceThreshold:\n                    heapq.heappush(heap, (currW + w, v))\n        return len(dist)", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        def getNumberOfNeighbors(city, graph):\n            heap = [(0, city)]\n            dist = {}\n            \n            while heap:\n                currW, u = heapq.heappop(heap)\n                if u in dist:\n                    continue\n                if u != city:    \n                    dist[u] = currW\n                for v, w in graph[u].items():\n                    if v in dist:\n                        continue\n                    if currW + w <= distanceThreshold:\n                        heapq.heappush(heap, (currW + w, v))\n            return len(dist)\n        \n        adjList = collections.defaultdict(dict)\n        for start, end, weight in edges:\n            adjList[start][end] = weight\n            adjList[end][start] = weight\n        \n        disconnected_cities = set([i for i in range(n)]) - adjList.keys()\n        if disconnected_cities:\n            return max(disconnected_cities)\n        \n        min_so_far = float('inf')\n        cities = []\n        \n        for city in adjList.keys():\n            count = getNumberOfNeighbors(city, adjList)\n\n            if count < min_so_far:\n                min_so_far = count\n                cities = [city]\n            elif count == min_so_far:\n                cities.append(city)\n        return max(cities)", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \n        graph = collections.defaultdict(list)\n        \n        for u, v, w in edges:\n            graph[u].append((v, w))\n            graph[v].append((u, w))\n            \n        def getNumberOfNeighbors(city):\n            heap = [(0, city)]\n            dist = {}\n            \n            while heap:\n                currW, u = heapq.heappop(heap)\n                if u in dist:\n                    continue\n                if u != city:    \n                    dist[u] = currW\n                for v, w in graph[u]:\n                    if v in dist:\n                        continue\n                    if currW + w <= distanceThreshold:\n                        heapq.heappush(heap, (currW + w, v))\n            return len(dist)\n        \n        return max([(getNumberOfNeighbors(city), city) for city in range(n)], key=lambda x: (-x[0], x[1]))[-1]", "from collections import defaultdict\nfrom heapq import heapify,heappush,heappop\nimport math\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \n        graph  = defaultdict(list)\n        \n        for i in range(len(edges)):\n            graph[edges[i][0]].append([edges[i][1],edges[i][2]])\n            graph[edges[i][1]].append([edges[i][0],edges[i][2]])\n            \n        res = [0]*n\n        \n        for i in range(n):\n            visited  = [False]*n\n            distance = [math.inf]*n\n            distance[i]=0\n            stack =[[0,i]]\n            count = 0\n            while(len(stack)!=0):\n                p = heappop(stack)\n                if p[0]>distanceThreshold:\n                    break\n                visited[p[1]] = True\n                for node in graph[p[1]]:\n                    if visited[node[0]]==False:\n                        if p[0]+node[1]<distance[node[0]]:\n                            distance[node[0]]= distance[p[1]]+node[1]\n                            heappush(stack,[distance[node[0]],node[0]])\n            count = 0\n            for j in range(n):\n                if visited[j]==True:\n                    count+=1\n            res[i]=count-1\n        m = math.inf\n        pos = 0\n        for i in range(n):\n            if res[i]<=m:\n                m =res[i]\n                pos = i\n                \n        return pos", "class Solution:\n    def findTheCity(self, n, edges, threshold):\n        adj=[[] for _ in range(n)]\n        for u,v,w in edges:\n            adj[u].append((w,v))\n            adj[v].append((w,u))\n\n        ans=0\n        min_cities=100\n        for x in range(n):\n            cur_cities=0\n            vis={x}\n            dist=[threshold+1]*n\n            hp=[(0,x)]\n            while hp:\n                d,u=heappop(hp)\n                for w,v in adj[u]:\n                    if d+w<=threshold and d+w<dist[v]:\n                        dist[v]=d+w\n                        vis.add(v)\n                        heappush(hp,(d+w,v))\n            if len(vis)<=min_cities:\n                min_cities=len(vis)\n                ans=x\n        \n        return ans", "from collections import defaultdict\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        '''\n        # Notes:\n            return the city with the smallest number of cities that are reachable through some path\n        # Appraoch:\n            Dijkstra\n        '''\n        # build the graph\n        graph = defaultdict(dict)\n        for city1, city2, weight in edges:\n            graph[city1][city2] = weight\n            graph[city2][city1] = weight\n\n        res, res_reachable = None, float('inf')\n        for i in range(n):\n            visited = set()\n            unvisited = set()\n            shortest_distance = [float('inf')] * n\n            for j in range(n):\n                if j == i:\n                    visited.add(j)\n                    shortest_distance[i] = 0\n                else:\n                    unvisited.add(j)\n            cur = i\n            reachable = defaultdict(set)\n            while cur != None:\n                for neighbor in graph[cur]:\n                    if neighbor not in visited:\n                        if shortest_distance[cur] + graph[cur][neighbor] <= distanceThreshold:\n                            reachable[i].add(neighbor)\n                            if shortest_distance[cur] + graph[cur][neighbor] < shortest_distance[neighbor]:\n                                shortest_distance[neighbor] = shortest_distance[cur] + graph[cur][neighbor]\n           \n                cur = None\n                for city in unvisited:\n                    if shortest_distance[city] != float('inf'):\n                        if cur == None:\n                            cur = city\n                        else:\n                            if shortest_distance[city] < shortest_distance[cur]:\n                                cur = city\n                if cur != None:\n                    visited.add(cur)\n                    unvisited.remove(cur)\n\n            if len(reachable[i]) <= res_reachable:\n                res_reachable = len(reachable[i])\n                res = i\n                \n        return res", "class Solution:\n    def dijkstra(self, graph, src):\n        dist, visited = {}, collections.defaultdict(bool, {src: True})\n        for u in graph:\n            dist[u] = float('inf')\n        dist[src] = 0\n\n        heap = [(0, src)]\n        while heap:\n            cur, city = heapq.heappop(heap)\n            visited[city] = True\n            for to, weight in graph[city]:\n                if not visited[to] and dist[to] > cur + weight:\n                    dist[to] = cur + weight\n                    heapq.heappush(heap, (dist[to], to))\n\n        return dist\n\n\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        graph = collections.defaultdict(list)\n        for u, v, w in edges:\n            graph[u].append((v, w))\n            graph[v].append((u, w))\n\n        neighbors = collections.defaultdict(int)\n        for city in graph:\n            for c, dist in list(self.dijkstra(graph, src=city).items()):\n                if city != c and dist <= distanceThreshold:\n                    neighbors[city] += 1\n\n        for i in range(n):\n            if neighbors[i]: pass\n\n        answer, min_neighbors = -1, float('inf')\n        for city, num in list(neighbors.items()):\n            if num < min_neighbors or (num == min_neighbors and city > answer):\n                answer = city\n                min_neighbors = num\n\n        return answer\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        h=collections.defaultdict(list)\n        for i in edges:\n            h[i[0]].append((i[1],i[2]))\n            h[i[1]].append((i[0],i[2]))\n        #print(h)\n        c=0\n        no=101\n        for i in range(n):\n            b=set()\n            q=[]\n            heapq.heappush(q,(0,i,-1))\n            while q:\n                x=heapq.heappop(q)\n                if x[1] in b:\n                    continue\n                b.add(x[1])\n                #print(x,q,b)\n                for j in h[x[1]]:\n                    if j[1]+x[0]<=distanceThreshold and j[0]!=x[2] and j[0] not in b:\n                        heapq.heappush(q,(j[1]+x[0],j[0],x[1]))\n            if len(b)-1<=no:\n                no=len(b)-1\n                c=i\n        return c\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        h=collections.defaultdict(list)\n        for i in edges:\n            h[i[0]].append((i[1],i[2]))\n            h[i[1]].append((i[0],i[2]))\n        #print(h)\n        c=0\n        no=101\n        for i in range(n):\n            b=set()\n            q=[]\n            heapq.heappush(q,(0,i,-1))\n            while q:\n                x=heapq.heappop(q)\n                if x[1] in b:\n                    continue\n                b.add(x[1])\n                #print(x,q,b)\n                for j in h[x[1]]:\n                    if j[1]+x[0]<=distanceThreshold and j[0]!=x[2] and j[0] not in b:\n                        heapq.heappush(q,(j[1]+x[0],j[0],x[1]))\n            if len(b)-1<=no:\n                no=len(b)-1\n                c=i\n                print((len(b)-1))\n        return c\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        adj = collections.defaultdict(dict)\n        for a,b,c in edges:\n            adj[a][b] = adj[b][a] = c\n        def bfs(s, distanceThreshold):\n            visited = [False] * n\n            dist = [float('inf')] * n\n            frontier = [(0, s)]\n            visited[s] = True\n            dist[s] = 0\n            while not all(visited) and frontier:\n                d, s = heapq.heappop(frontier)\n                if d > distanceThreshold: break\n                dist[s] = d\n                visited[s] = True\n                for t in adj[s]:\n                    if not visited[t]:\n                        heapq.heappush(frontier, (d + adj[s][t], t))\n            return len([d for d in dist if d <= distanceThreshold])\n        res = 0\n        count = n\n        for i in range(n):\n            c = bfs(i, distanceThreshold)\n            if c <= count:\n                res = max(res, i)\n                count = c\n        return res\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        adj = collections.defaultdict(dict)\n        for a,b,c in edges:\n            adj[a][b] = adj[b][a] = c\n        def bfs(s, distanceThreshold):\n            visited = [False] * n\n            dist = [float('inf')] * n\n            frontier = [(0, s)]\n            # visited[s] = True\n            # dist[s] = 0\n            while not all(visited) and frontier:\n                d, s = heapq.heappop(frontier)\n                if d > distanceThreshold: break\n                dist[s] = d\n                visited[s] = True\n                for t in adj[s]:\n                    if not visited[t]:\n                        heapq.heappush(frontier, (d + adj[s][t], t))\n            return len([d for d in dist if d <= distanceThreshold])\n        res = 0\n        count = n\n        for i in range(n):\n            c = bfs(i, distanceThreshold)\n            if c <= count:\n                res = max(res, i)\n                count = c\n        return res\n", "from typing import List\nfrom collections import defaultdict\nfrom heapq import heappush, heappop\n\nclass Solution:\n\\tdef findTheCityFloydWarshall(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n\\t\\tdist = [[float('inf')] * n for _ in range(n)]\n\\t\\tfor u, v, w in edges:\n\\t\\t\\tdist[u][v] = dist[v][u] = w # bidirectional edges\n\\t\\tfor i in range(n):\n\\t\\t\\tdist[i][i] = 0\n\n\\t\\t# floyd-warshall\n\\t\\tfor k in range(n):\n\\t\\t\\tfor i in range(n):\n\\t\\t\\t\\tfor j in range(n):\n\\t\\t\\t\\t\\tdist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])\n\\t\\t\n\\t\\tres = {sum(v <= distanceThreshold for v in dist[u]): u for u in range(n)}\n\\t\\treturn res[min(res)]\n\\t\n\\tdef findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n\\t\\tgraph = defaultdict(list)\n\\t\\tfor u, v, w in edges:\n\\t\\t\\tgraph[u].append((v, w))\n\\t\\t\\tgraph[v].append((u, w))\n\n\\t\\tans = [float('inf'), float('inf')]\n\n\\t\\tfor i in range(n):\n\\t\\t\\tpq = [(0, i)]\n\\t\\t\\tdist = [float('inf')] * n\n\\t\\t\\tdist[i] = 0\n\\t\\t\\tvisit = [False] * n\n\n\\t\\t\\twhile pq:\n\\t\\t\\t\\tdist_u, u = heappop(pq)\n\\t\\t\\t\\tvisit[i] = True\n\\t\\t\\t\n\\t\\t\\t\\tfor v, w in graph[u]:\n\\t\\t\\t\\t\\tif not visit[v]:\n\\t\\t\\t\\t\\t\\tif dist[v] > dist[u] + w:\n\\t\\t\\t\\t\\t\\t\\tdist[v] = dist[u] + w\n\\t\\t\\t\\t\\t\\t\\tif dist[v] <= distanceThreshold:\n\\t\\t\\t\\t\\t\\t\\t\\theappush(pq, (dist[v], v))\n\n\\t\\t\\tcnt = 0\n\\t\\t\\tfor d in dist:\n\\t\\t\\t\\tif d <= distanceThreshold: cnt += 1\n\\t\\t\\t\n\\t\\t\\tif cnt < ans[0]:\n\\t\\t\\t\\tans = [cnt, i]\n\\t\\t\\telif cnt == ans[0]:\n\\t\\t\\t\\tif i > ans[1]:\n\\t\\t\\t\\t\\tans = [cnt, i]\n\\t\\t\n\\t\\treturn ans[1]", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        graph = [[float(\\\"inf\\\") for _ in range(n)] for _ in range(n)]\n        \n        for a in edges:\n            graph[a[0]][a[1]] = a[2]\n            graph[a[1]][a[0]] = a[2]\n            \n        for i in range(n):\n            graph[i][i] = 0\n            \n            \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    if graph[i][j]>graph[i][k]+graph[k][j]:\n                        graph[i][j] = graph[i][k]+graph[k][j]\n                        \n        count = float(\\\"inf\\\")\n        node = 0\n        for i in range(n):\n            a = graph[i]\n            c = [x for x in a if x<=distanceThreshold]\n            if len(c)<=count:\n                count = len(c)\n                node = i\n                \n        return node\n            \n                    \n                    \n                    \n                \n        ", "def init_graph(edges, n): \n    graph = [[] for _ in range(n)]\n    for src, dest, weight in edges: \n        graph[src].append((dest, weight))\n        graph[dest].append((src, weight))\n    return graph\n\ndef run_bfs(src, graph, threshold, n): \n    q = [(0, src)]\n    distances = [math.inf for i in range(n)]\n    distances[src] = 0\n    res = 0\n    while(q): \n        distance, node = heapq.heappop(q)\n        edges = graph[node]\n        print(\\\"Visiting: \\\" + str(node))\n        for nbr_node, weight in edges: \n            updated_distance = distance + weight\n            if distances[nbr_node] > updated_distance and updated_distance<=threshold: \n                print(\\\"Neighbor: \\\" + str(nbr_node) + \\\" distance: \\\" + str(updated_distance))\n                if distances[nbr_node] == math.inf: \n                    print(\\\"Updating for: \\\" + str(nbr_node))\n                    res = res + 1\n                distances[nbr_node] = updated_distance\n                heapq.heappush(q, (updated_distance, nbr_node))\n    print(\\\"Returning: \\\" + str(res))\n    return res \n\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        if n==0 or not edges: \n            return -1\n        \n        graph = init_graph(edges, n)\n        min_nbrs = math.inf\n        min_nbrs_city = -1\n        for i in range(n): \n            num_nbrs = run_bfs(i, graph, distanceThreshold, n)\n            if num_nbrs <= min_nbrs: \n                min_nbrs = num_nbrs\n                min_nbrs_city = max(min_nbrs_city, i)\n            \n        return min_nbrs_city \n    \n    \n    \n        \n            ", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        dist = [[float('inf')]*n for _ in range(n)]\n        next_city = [[None]*n for _ in range(n)]\n        \n        for edge in edges:\n            dist[edge[0]][edge[1]] = edge[2]\n            dist[edge[1]][edge[0]] = edge[2]\n            next_city[edge[0]][edge[1]] = edge[1]\n        \n        for city in range(n):\n            dist[city][city] = 0\n            next_city[city][city] = city\n            \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    if dist[i][j] > dist[i][k] + dist[k][j]:\n                        dist[i][j] = dist[i][k] + dist[k][j]\n                        next_city[i][j] = next_city[i][k]\n        city_sum_under_thresh = [0]*n\n        for i in range(n):\n            city_sum_under_thresh[i] += len([ distance for index, distance in enumerate(dist[i]) if distance <= distanceThreshold if index!= i])\n        return min([ (index, count) for index, count in enumerate(city_sum_under_thresh)], key = lambda x: (x[1], -x[0]))[0]", "# \uc774\uc6c3\uc218\uac00 \uac00\uc7a5 \uc801\uc740 \ub178\ub4dc \ucc3e\uae30\n# \uc774\uc6c3\uc218\uac00 \uac19\ub2e4\uba74 \ubc88\ud638\uac00 \uac00\uc7a5 \ud070 \ub178\ub4dc \ubc18\ud658\n\n# 1. \ubaa8\ub4e0 \ub178\ub4dc \ub2e4\uc775\uc2a4\ud2b8\ub77c\n# 2. \ud50c\ub85c\uc774\ub4dc\uc640\uc0ec\n# \uc6b0\uc120 adj \ub9cc\ub4e4\uae30\n# adj\uc5d0 \uc5f0\uacb0\ub418 \uc788\ub294 \ubd80\ubd84 \uac12 \ub123\uc5b4\uc8fc\uae30\n\n# if adj[i][j] + adj[j][k] < adj[i][k]\n# adj[i][k] = adj[i][j] + adj[j][k]\ndef floydWarshall(adj, n):\n#     \ucc98\uc74c\uc5d0 \ucd9c\ubc1c\uc9c0, \ub3c4\ucc29\uc9c0, \uacbd\uc720\uc9c0 \uc21c\uc11c\ub85c \ud588\uc744 \ub54c\ub294 \ud2c0\ub9bc \uc65c\uc77c\uae4c?\n    for k in range(n): # \uacbd\uc720\uc9c0\n        for i in range(n): # \ucd9c\ubc1c\uc9c0\n            for j in range(n): # \ub3c4\ucc29\uc9c0\n                stopOver = adj[i][k] + adj[k][j]\n                if(stopOver < adj[i][j]):\n                    adj[i][j] = stopOver\n\nclass Solution:                 \n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        INFI = 2 ** 31\n        adj = [[INFI for _ in range(n)] for _ in range(n)]                \n        answer = 0\n        neighbors = []\n        for x in range(n):\n            adj[x][x] = 0\n        \n        for edge in edges:\n            adj[edge[0]][edge[1]] = edge[2]\n            adj[edge[1]][edge[0]] = edge[2]\n        floydWarshall(adj, n)        \n        # print(adj)\n#         \uc774\uc6c3 \ucd94\uac00\n        for node in adj:\n            count = 0 # \uc774\uc6c3 \uc218\n            for distance in node:\n                if distance <= distanceThreshold:\n                    count += 1\n            neighbors.append(count-1)\n        \n        # print(neighbors)\n        minCount = min(neighbors)\n        # print(neighbors)\n        for i, neighCount in enumerate(neighbors):\n            if(minCount == neighCount):\n                answer = i                \n                \n        return answer", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        # Floyd-Warshall algo\n        _c = [float('inf')] * n\n        dv = [list(_c) for _ in range(n)]\n        for i in range(n):\n            dv[i][i] = 0\n        for l, r, w in edges:   # Bidirectional\n            dv[l][r] = w\n            dv[r][l] = w\n        \n        for k in range(n):\n            for r in range(n):\n                for c in range(n):\n                    tk = dv[r][k] + dv[k][c]    # R->C through K\n                    if dv[r][c] > tk:\n                        dv[r][c] = tk\n        smallest = 0\n        mc = n+1\n        \n        for r in range(n):\n            cities = 0\n            for c in range(n):\n                if dv[r][c] <= distanceThreshold:\n                    print(f'{r} -> {c}; {dv[r][c]} <= {distanceThreshold}')\n                    cities += 1\n            if cities <= mc:\n                smallest = r\n                mc = cities\n        return smallest\n                \n    \n    \\\"\\\"\\\" Dijkstra's method\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        oe = {}\n        for l, r, w in edges:       \n            if l not in oe:\n                oe[l] = set()\n            if r not in oe:\n                oe[r] = set()\n            oe[l].add((r, w))\n            oe[r].add((l, w))\n        \n        def dks(been, c, t):\n            cw = been[c]        # Current Weight\n            if c not in oe:     # No route to any other city\n                return\n            pending = set()\n            for other, weight in oe[c]:\n                ow = weight + cw     # From current city to the other city weight\n                if ow > distanceThreshold:\n                    continue\n                \n                if other not in been:\n                    been[other] = ow\n                    pending.add(other)\n                    continue\n                if been[other] > ow: # Through this city is more effcient\n                    been[other] = ow\n                    pending.add(other)\n\n            for o in pending:\n                dks(been, o, t)\n    \n            \n        smallest = 0\n        mc = n+1\n        for city in range(n):\n            dv = {city: 0}\n            dks(dv, city, distanceThreshold)\n            # print(dv)\n            cities = len(dv.keys()) - 1\n            if cities <= mc:\n                smallest = city\n                mc = cities\n        return smallest\n        \\\"\\\"\\\"\n        \n        ", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], dist: int) -> int:\n        if n==2:\n            return 1\n        \n        graph = [[float('inf')]*n for _ in range(n)] \n        for s,e,w in edges:\n            graph[s][e] = w\n            graph[e][s] = w\n        \n        \n        for i in range(n):\n            graph[i][i] = 0\n        \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    if graph[i][j] > (d:= graph[i][k] + graph[k][j]):\n                            graph[i][j] = d\n        \n        nei = {len(list(filter(lambda x: 0 < x <= dist, graph[i]))): i for i in range(n)}\n        # print(nei)\n        # print(graph)\n        return nei[min(nei)]", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        g = collections.defaultdict(list)\n        for f, t, w in edges:\n            g[f].append((t, w))\n            g[t].append((f, w))\n        \n        def bfs(i):\n            q = [(0, i)]\n            dist = [distanceThreshold + 1] * n\n            visited = {i}\n            while q:\n                w, j = heapq.heappop(q)\n                if w > dist[j]:\n                    continue\n                visited.add(j)\n                for k, w_ in g[j]:\n                    d = w + w_\n                    if k not in visited and d <= distanceThreshold and d < dist[k]:\n                        heapq.heappush(q, (d, k))\n                        dist[k] = d\n            return len(visited)\n        \n        return -min([(bfs(i), -i) for i in range(n)])[1]", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        dist = [[float('inf')] * n for _ in range(n)]\n        for u, v, w in edges:\n            dist[u][v] = w\n            dist[v][u] = w\n        for u in range(n):\n            dist[u][u] = 0\n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    if dist[i][j] > (d := dist[i][k] + dist[k][j]):\n                        dist[i][j] =  d\n        neighbors = {len(list(filter(lambda x: 0 < x <= distanceThreshold, dist[i]))): i for i in range(n)}\n        return neighbors[min(neighbors)]", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], threshold: int) -> int:\n        graph = [[] for i in range(n)]\n        for src, dst, weight in edges:\n            graph[src].append((weight, dst))\n            graph[dst].append((weight, src))\n\n        def find_num_closest(city):\n            visited = set()\n            q = [(0, city)]\n            while q:\n                dist, c = heappop(q)\n                if c in visited:\n                    continue\n                visited.add(c)\n                for weight, dest in graph[c]:\n                    if dist + weight <= threshold:\n                        heappush(q, (dist + weight, dest))\n            return len(visited)\n\n        min_val = float('inf')\n        min_city = None\n        for i in range(n):\n            closest = find_num_closest(i)\n            #print(\\\"city {} has {} within threshold\\\".format(i, closest))\n            if closest <= min_val:\n                min_val = closest\n                min_city = i\n        return min_city", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        THRESHOLD_MAX = 10001\n        dist = [[THRESHOLD_MAX for _ in range(n)] for _ in range(n)]\n        \n        for edge in edges:\n            dist[edge[0]][edge[1]] = edge[2]\n            dist[edge[1]][edge[0]] = edge[2]\n        \n        for i in range(n):\n            dist[i][i] = 0\n            \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    if i != j:\n                        intermediate_dist = dist[i][k] + dist[k][j]\n                        if intermediate_dist < dist[i][j]:\n                            dist[i][j] = intermediate_dist\n                            \n        min_threshold_cities = n\n        curr = -1\n        for i in range(n):\n            count = 0\n            for j in range(n):\n                if i != j and dist[i][j] <= distanceThreshold:\n                    count +=1\n            \n            if count <= min_threshold_cities:\n                min_threshold_cities = count\n                curr = i\n        return curr        \n            \n", "from collections import defaultdict\nclass Solution:\n    \n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        g = [[math.inf] * n for _ in range(n)]\n        for i in range(n):\n            g[i][i] = 0\n        for e in edges:\n            g[e[0]][e[1]] = e[2]\n            g[e[1]][e[0]] = e[2]\n       \n\\t   # Floyd Warshall's shortest path\n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    if g[i][j] > g[i][k] + g[k][j]:\n                        g[i][j] = g[i][k] + g[k][j]\n        res_node, res_connected = -1, math.inf\n        for i in range(n):\n            conn = 0\n            for j in range(n):\n                if g[i][j] <= distanceThreshold:\n                    conn += 1\n            if conn <= res_connected:\n                res_node, res_connected = i, conn\n        return res_node\n            \n        ", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], D: int) -> int:\n        # floyd alg to generate all pairs shortest dists\n        dists = [ [ inf for _ in range(n) ] for _ in range(n) ]\n        \n        for a, b, w in edges:\n            dists[a][b] = dists[b][a] = w\n        \n        for i in range(n):\n            dists[i][i] = 0\n        \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    if dists[i][k] + dists[k][j] < dists[i][j]:\n                        dists[i][j] = dists[j][i] = dists[i][k] + dists[k][j] \n        \n        # print(dists)\n        \n        # loop through each node to find all feasible neighbours\n        return min(list(range(n)), key = lambda i: (sum(int(d <= D) for d in dists[i]), -i))\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        def method1():\n            graph=collections.defaultdict(list)\n            for s,d,w in edges:\n                graph[s].append((d,w))\n                graph[d].append((s,w))\n                \n            \n            def dijkstrase(s):\n                queue=[(0,s)]\n                seen={s:0}\n                \n                while queue:\n                    w,s=heapq.heappop(queue)\n                    for nei,dw in graph[s]:\n                        if nei not in seen or w+dw<seen[nei]:\n                            seen[nei]=w+dw\n                            heapq.heappush(queue, (w+dw,nei))\n                \n                return seen\n            \n            distances=[dijkstrase(i) for i in range(n)]\n            #print(distances)\n            ans=[]\n            for i in range(n):\n                total=0\n                for k,v in list(distances[i].items()):\n                    if 0<v<=distanceThreshold:\n                        total+=1\n                ans.append(total)\n                \n            #print(ans)\n            return max([i for i in range(n) if ans[i]==min(ans)])\n            \n        return method1()\n            \n            \n                    \n                \n", "from collections import defaultdict\nclass Solution:\n    \n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        g = [[float('inf')] * n for _ in range(n)]\n        for i in range(n):\n            g[i][i] = 0\n        for e in edges:\n            g[e[0]][e[1]] = e[2]\n            g[e[1]][e[0]] = e[2]\n       \n\\t   # Floyd Warshall's shortest path\n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    if g[i][j] > g[i][k] + g[k][j]:\n                        g[i][j] = g[i][k] + g[k][j]\n        res_node, res_connected = -1, math.inf\n        for i in range(n):\n            conn = 0\n            for j in range(n):\n                if g[i][j] <= distanceThreshold:\n                    conn += 1\n            if conn <= res_connected:\n                res_node, res_connected = i, conn\n        return res_node\n            \n        ", "from typing import List\nfrom collections import defaultdict\nfrom heapq import heappush, heappop\n\nclass Solution:\n\\tdef findTheCityFloydWarshall(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n\\t\\tdist = [[float('inf')] * n for _ in range(n)]\n\\t\\tfor u, v, w in edges:\n\\t\\t\\tdist[u][v] = dist[v][u] = w # bidirectional edges\n\\t\\tfor i in range(n):\n\\t\\t\\tdist[i][i] = 0\n\n\\t\\t# floyd-warshall\n\\t\\tfor k in range(n):\n\\t\\t\\tfor i in range(n):\n\\t\\t\\t\\tfor j in range(n):\n\\t\\t\\t\\t\\tdist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])\n\\t\\t\n\\t\\tres = {sum(v <= distanceThreshold for v in dist[u]): u for u in range(n)}\n\\t\\treturn res[min(res)]\n\\t\n\\tdef findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n\\t\\tgraph = defaultdict(dict)\n\\t\\tfor u, v, w in edges:\n\\t\\t\\tgraph[u][v] = graph[v][u] = w\n\n\\t\\tans = [float('inf'), float('inf')]\n\n\\t\\tfor i in range(n):\n\\t\\t\\tpq = [(0, i)]\n\\t\\t\\tdist = [float('inf')] * n\n\\t\\t\\tdist[i] = 0\n\\t\\t\\tvisit = [False] * n\n\n\\t\\t\\twhile pq:\n\\t\\t\\t\\tdist_u, u = heappop(pq)\n\\t\\t\\t\\tvisit[i] = True\n\\t\\t\\t\n\\t\\t\\t\\tfor v in graph[u]:\n\\t\\t\\t\\t\\tif not visit[v]:\n\\t\\t\\t\\t\\t\\tif dist[v] > dist[u] + graph[u][v]:\n\\t\\t\\t\\t\\t\\t\\tdist[v] = dist[u] + graph[u][v]\n\\t\\t\\t\\t\\t\\t\\tif dist[v] <= distanceThreshold:\n\\t\\t\\t\\t\\t\\t\\t\\theappush(pq, (dist[v], v))\n\n\\t\\t\\tcnt = 0\n\\t\\t\\tfor d in dist:\n\\t\\t\\t\\tif d <= distanceThreshold: cnt += 1\n\\t\\t\\t\n\\t\\t\\tif cnt < ans[0]:\n\\t\\t\\t\\tans = [cnt, i]\n\\t\\t\\telif cnt == ans[0]:\n\\t\\t\\t\\tif i > ans[1]:\n\\t\\t\\t\\t\\tans = [cnt, i]\n\\t\\t\n\\t\\treturn ans[1]", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        dist = [[float('inf')] * n for _ in range(n)]\n        for u, v, w in edges:\n            dist[u][v] = w\n            dist[v][u] = w\n        for u in range(n):\n            dist[u][u] = 0\n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    if dist[i][j] > (d := dist[i][k] + dist[k][j]):\n                        dist[i][j] =  d\n        ans = {}\n        for i,a in enumerate(dist):\n            for b in a:\n                if(b<=distanceThreshold):\n                    if(i in ans):\n                        ans[i] +=1\n                    else:\n                        ans[i] = 1\n        ans2 = 0\n        minValue = 10000000\n\n        for key, value in list(ans.items()):\n            if(value <= minValue):\n                minValue = value\n                ans2 = key\n        return ans2\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \n        val = float('inf')\n        arr = [[val for i in range(0,n)] for j in range(0,n)]\n        \n        for x in edges:\n            arr[x[0]][x[1]]=x[2]\n            arr[x[1]][x[0]]=x[2]\n            \n        for i in range(0,n):\n            arr[i][i]=0\n        \n        for k in range(0,n):\n            for i in range(0,n):\n                for j in range(0,n):\n                    if arr[i][j] > arr[i][k] + arr[k][j]: \n                        arr[i][j] = arr[i][k] + arr[k][j]\n        \n        mn = val\n        for i in range(0,n):\n            count = 0\n            for x in arr[i]:\n                if x<=distanceThreshold:\n                    count+=1\n            if count<=mn:\n                mn = count\n                ret = i\n                \n        return ret\n        \n        \n        \n        \n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        g = defaultdict(deque)\n        for a,b,d in edges:\n            g[a].append((b,d))\n            g[b].append((a,d))\n\n        def helper(node:int, threshold) -> int:\n            lookup = {}\n            heap = [(0,node)]\n            visited = set()\n            while heap:\n                d,u = heapq.heappop(heap)\n                if d <= threshold:\n                    visited.add(u)\n                if d > threshold:\n                    return len(visited)\n                if u in lookup and lookup[u] < d:\n                    continue\n                for v,w in g[u]:\n                    if v not in lookup or (w+d <= threshold and lookup[v] > w+d):\n                        lookup[v] = w+d\n                        heapq.heappush(heap,(w+d,v))\n            return len(visited)\n        min_nei, node = float('inf'), None\n        for i in range(n-1,-1,-1):\n            count = helper(i, distanceThreshold)\n            if count == 1:\n                return i\n            if count < min_nei:\n                min_nei = count\n                node = i\n        return node\n                    \n", "from collections import defaultdict\n\n\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        dmatrix = [[9999999999999999 for _ in range(n)] for _ in range(n)]\n        \n        for a, b, w in edges:\n            dmatrix[a][b] = w\n            dmatrix[b][a] = w\n            \n        for source in range(n):\n            dmatrix[source][source] = 0\n        \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    if dmatrix[i][j] > dmatrix[i][k] + dmatrix[k][j]:\n                        dmatrix[i][j] = dmatrix[i][k] + dmatrix[k][j]\n        \n        cities = [(sum([dist <= distanceThreshold for dist in dmatrix[city]]), -city) for city in range(n)]\n        _, best_city = list(sorted(cities))[0]\n        return -best_city", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        def method1():\n            graph=collections.defaultdict(list)\n            for s,d,w in edges:\n                graph[s].append((d,w))\n                graph[d].append((s,w))\n                \n            \n            def dijkstrase(s):\n                queue=[(0,s)]\n                seen={s:0}\n                \n                while queue:\n                    w,s=heapq.heappop(queue)\n                    for nei,dw in graph[s]:\n                        if nei not in seen or w+dw<seen[nei]:\n                            seen[nei]=w+dw\n                            heapq.heappush(queue, (w+dw,nei))\n                \n                return seen\n            \n            distances=[dijkstrase(i) for i in range(n)]\n            ans=[sum(0<v<=distanceThreshold for k,v in list(distances[i].items())) for i in range(n)]\n            return max([i for i in range(n) if ans[i]==min(ans)])\n            \n        return method1()\n            \n            \n                    \n                \n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        def method1():\n            graph=collections.defaultdict(list)\n            for s,d,w in edges:\n                graph[s].append((d,w))\n                graph[d].append((s,w))\n                \n            \n            def dijkstrase(s):\n                queue=[(0,s)]\n                seen={s:0}\n                \n                while queue:\n                    w,s=heapq.heappop(queue)\n                    for nei,dw in graph[s]:\n                        if nei not in seen or w+dw<seen[nei]:\n                            seen[nei]=w+dw\n                            heapq.heappush(queue, (w+dw,nei))\n                \n                return seen\n            \n            distances=[dijkstrase(i) for i in range(n)]\n            ans=[]\n            for i in range(n):\n                total=0\n                for k,v in list(distances[i].items()):\n                    if 0<v<=distanceThreshold:\n                        total+=1\n                ans.append(total)\n                \n            ans=[sum(0<v<=distanceThreshold for k,v in list(distances[i].items())) for i in range(n)]\n            return max([i for i in range(n) if ans[i]==min(ans)])\n            \n        return method1()\n            \n            \n                    \n                \n", "'''\nUsing Floyd-Warshall Algorithm\nReference: https://www.youtube.com/watch?v=oNI0rf2P9gE\n\nTC: O(V^3)\nSC: O(V^2)\n'''\nimport heapq\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        dist = [[float('inf')]*n for _ in range(n)]\n        graph = defaultdict(list)\n        for u, v, w in edges:\n            #graph[u].append((w,v))\n            #graph[v].append((w,u))\n            dist[u][v] = w\n            dist[v][u] = w\n            dist[u][u] = 0\n            dist[v][v]\n        \n        minCities = n\n        ans = -1\n        \n        '''\n        Considering all paths between i, j going through each k vertex\n        '''\n        for k in range(n):\n            for i in range(n):\n                numCities = 0\n                for j in range(n):\n                    if dist[i][j] > dist[i][k] + dist[k][j]:\n                        dist[i][j] = dist[i][k] + dist[k][j]\n                    \n                    if k == n-1:\n                        if dist[i][j] <= distanceThreshold:\n                            numCities += 1\n                \n                if k == n-1:\n                    if numCities <= minCities:\n                        ans = i\n                        minCities = numCities\n        \n        return ans\n                    \n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        graph = [[] for _ in range(n)]\n        for i, j, w in edges:\n            graph[i].append((j, w))\n            graph[j].append((i, w))\n        \n        result = []\n        for i in range(n):\n            queue = [(0, i)]\n            visited = set()\n            while queue:\n                distance, i = heapq.heappop(queue)\n                if i in visited:\n                    continue\n                visited.add(i)\n                for j, w in graph[i]:\n                    new_distance = distance + w\n                    if new_distance <= distanceThreshold and j not in visited:\n                        heapq.heappush(queue, (new_distance, j))\n            result.append(len(visited))\n        return min(list(range(n)), key=lambda x: (result[x], -x))\n        \n        \n        \n#         dp = [[float(\\\"inf\\\")] * n for _ in range(n)]\n#         for i in range(n):\n#             dp[i][i] = 0\n#         for i, j, w in edges:\n#             dp[i][j] = w\n#             dp[j][i] = w\n#         for i in range(n):\n#             for j in range(n):\n#                 if i != j:\n#                     for k in range(j + 1, n):\n#                         dp[j][k] = min(dp[j][k], dp[j][i] + dp[i][k])\n#                         dp[k][j] = dp[j][k]\n#         return min(range(n), key=lambda i: (sum(dist <= distanceThreshold for dist in dp[i]), -i))\n        \n        \n        \n#         graph = [[] for _ in range(n)]\n#         for i, j, w in edges:\n#             graph[i].append((j, w))\n#             graph[j].append((i, w))\n        \n#         result = []\n#         for i in range(n):\n#             queue = [(0, i)]\n#             visited = set()\n#             while queue:\n#                 distance, i = heapq.heappop(queue)\n#                 if i in visited:\n#                     continue\n#                 visited.add(i)\n#                 for j, w in graph[i]:\n#                     if distance + w <= distanceThreshold:\n#                         heapq.heappush(queue, (distance + w, j))\n#             visited.remove(i)\n#             result.append(list(visited))\n#         return min(range(n), key=lambda x: (len(result[x]), -x))\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        dis = [[float('inf')] * n for _ in range(n) ]\n        for u,v,w in edges:\n            dis[u][v] = dis[v][u] = w\n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    if  i != j and dis[i][j] > dis[i][k] + dis[k][j]:\n                        dis[i][j] = dis[i][k] + dis[k][j]\n        d = {i: len([dis[i][j] for j in range(n) if dis[i][j] <= distanceThreshold]) for i in range(n)}\n        minv = float('inf')\n        res = -1\n        for i in reversed(range(n)):\n            if d[i] < minv:\n                res = i\n                minv = d[i]\n        return res", "from typing import List\nfrom collections import defaultdict\nfrom heapq import heappush, heappop\n\nclass Solution:\n\\tdef findTheCityFloydWarshall(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n\\t\\tdist = [[float('inf')] * n for _ in range(n)]\n\\t\\tfor u, v, w in edges:\n\\t\\t\\tdist[u][v] = dist[v][u] = w # bidirectional edges\n\\t\\tfor i in range(n):\n\\t\\t\\tdist[i][i] = 0\n\n\\t\\t# floyd-warshall\n\\t\\tfor k in range(n):\n\\t\\t\\tfor i in range(n):\n\\t\\t\\t\\tfor j in range(n):\n\\t\\t\\t\\t\\tdist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])\n\\t\\t\n\\t\\tres = {sum(v <= distanceThreshold for v in dist[u]): u for u in range(n)}\n\\t\\treturn res[min(res)]\n\\t\n\\tdef findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n\\t\\tgraph = defaultdict(dict)\n\\t\\tfor u, v, w in edges:\n\\t\\t\\tgraph[u][v] = graph[v][u] = w\n\n\\t\\tans = [float('inf'), float('inf')]\n\n\\t\\tfor i in range(n):\n\\t\\t\\tpq = [(0, i)]\n\\t\\t\\tdist = [float('inf')] * n\n\\t\\t\\tdist[i] = 0\n\n\\t\\t\\twhile pq:\n\\t\\t\\t\\tdist_u, u = heappop(pq)\n\\t\\t\\t\n\\t\\t\\t\\tfor v in graph[u]:\n\\t\\t\\t\\t\\tif dist[v] >  dist[u] + graph[u][v]:\n\\t\\t\\t\\t\\t\\tdist[v] = dist[u] + graph[u][v]\n\\t\\t\\t\\t\\t\\theappush(pq, (dist[v], v))\n\n\\t\\t\\tcnt = 0\n\\t\\t\\tfor d in dist:\n\\t\\t\\t\\tif d <= distanceThreshold: cnt += 1\n\\t\\t\\t\n\\t\\t\\tif cnt < ans[0]:\n\\t\\t\\t\\tans = [cnt, i]\n\\t\\t\\telif cnt == ans[0]:\n\\t\\t\\t\\tif i > ans[1]:\n\\t\\t\\t\\t\\tans = [cnt, i]\n\\t\\t\n\\t\\treturn ans[1]", "class Solution:\n    def dfs(self, q, D, V, k):\n        Q = [q]\n        V[q] = 0\n        while Q:\n            T = []\n            for nd in Q:\n                W = V[nd]\n                for n,w in D[nd]:\n                    cl = W + w\n                    cr = V[n]                \n                    if cl < cr and cl <= k:\n                        V[n] = cl\n                        T.append(n)\n            Q = T\n        return {a:b for a,b in list(V.items()) if b != sys.maxsize}\n    \n    def findTheCity(self, N: int, E: List[List[int]], k: int) -> int:\n        D = collections.defaultdict(list)\n        \n        for f,t,w in E:\n            D[f].append((t, w))\n            D[t].append((f, w))\n        \n        R = dict()\n        mn = sys.maxsize\n        for q in range(N):\n            V = self.dfs(q, D, collections.defaultdict(lambda:sys.maxsize), k)\n            R[q] = V\n            if mn > len(V):\n                mn = len(V)\n            \n        R = {a:b for a,b in list(R.items()) if len(b) == mn}\n        return max(R.keys())\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \n        graph=collections.defaultdict(list)\n        for u,v,w in edges:\n            graph[u].append([w,v])\n            graph[v].append([w,u])\n        count=[0]*n\n        def find_cities_k(vertex,vis):\n            q=[]\n            #[distance_covered,vertex]\n            heapq.heappush(q,[0,vertex])\n            while q:\n                dis,node=heapq.heappop(q)\n                if node in vis:\n                    continue\n                vis.add(node)\n                if dis<=distanceThreshold:\n                    if vertex!=node:\n                        count[vertex]+=1\n                for w,neigh in graph[node]:\n                    if neigh not in vis:\n                        heapq.heappush(q,[dis+w,neigh])\n        for i in range(n):\n            find_cities_k(i,set())\n        min_=10000\n        city_=-1\n        for i in range(n):\n            if count[i]<=min_:\n                min_=count[i]\n                city_=i\n        return city_        \n            \n                        \n                \n        \n                  \n        \n                \n            \n            \n            \n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \n        graph = defaultdict(list)\n        output = []\n        \n        for u, v, w in edges:\n            graph[u].append((v, w))\n            graph[v].append((u, w))\n        \n        for i in range(n):\n            \n            #distance , city 2 , original\n            queue = [(0,i)]\n            curr = {}\n            \n            while queue:\n                dist, node = heapq.heappop(queue)\n                \n                if node in curr and dist >= curr[node]:\n                    continue\n                \n                curr[node] = dist\n                \n                for city, distance in graph[node]:\n                    if distance + dist <= distanceThreshold:\n                        heapq.heappush(queue,(distance + dist , city))\n            \n            output.append(len(curr)-1)\n        \n        for i in range(len(output)-1,-1,-1):\n            if output[i] == min(output):\n                return i", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        graph = [[] for _ in range(n)]\n        for i, j, w in edges:\n            graph[i].append((j, w))\n            graph[j].append((i, w))\n        \n        result = []\n        for i in range(n):\n            queue = [(0, i)]\n            distances = defaultdict(lambda: distanceThreshold)\n            visited = set()\n            while queue:\n                distance, i = heapq.heappop(queue)\n                if i in visited:\n                    continue\n                visited.add(i)\n                for j, w in graph[i]:\n                    new_distance = distance + w\n                    if new_distance <= distances[j] and j not in visited:\n                        distances[j] = new_distance\n                        heapq.heappush(queue, (new_distance, j))\n            result.append(len(visited))\n        return min(list(range(n)), key=lambda x: (result[x], -x))\n        \n        \n        \n#         dp = [[float(\\\"inf\\\")] * n for _ in range(n)]\n#         for i in range(n):\n#             dp[i][i] = 0\n#         for i, j, w in edges:\n#             dp[i][j] = w\n#             dp[j][i] = w\n#         for i in range(n):\n#             for j in range(n):\n#                 if i != j:\n#                     for k in range(j + 1, n):\n#                         dp[j][k] = min(dp[j][k], dp[j][i] + dp[i][k])\n#                         dp[k][j] = dp[j][k]\n#         return min(range(n), key=lambda i: (sum(dist <= distanceThreshold for dist in dp[i]), -i))\n        \n        \n        \n#         graph = [[] for _ in range(n)]\n#         for i, j, w in edges:\n#             graph[i].append((j, w))\n#             graph[j].append((i, w))\n        \n#         result = []\n#         for i in range(n):\n#             queue = [(0, i)]\n#             visited = set()\n#             while queue:\n#                 distance, i = heapq.heappop(queue)\n#                 if i in visited:\n#                     continue\n#                 visited.add(i)\n#                 for j, w in graph[i]:\n#                     if distance + w <= distanceThreshold:\n#                         heapq.heappush(queue, (distance + w, j))\n#             visited.remove(i)\n#             result.append(list(visited))\n#         return min(range(n), key=lambda x: (len(result[x]), -x))\n", "class Solution:\n    \n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        #22:02-\n        \n        dists = [[distanceThreshold + 1 for i in range(n)] for j in range(n)]\n        for s, e, w in edges:\n            dists[s][e] = w\n            dists[e][s] = w\n        \n        for i in range(n):\n            dists[i][i] = 0        \n        \n        #\ubaa8\ub4e0 \uc30d\uc758 \ucd5c\ub2e8 \uac70\ub9ac\n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    if dists[i][k] + dists[k][j] > distanceThreshold:\n                        continue\n                    elif dists[i][j] is None:\n                        dists[i][j] = dists[i][k] + dists[k][j]\n                    elif dists[i][k] + dists[k][j] < dists[i][j]:\n                        dists[i][j] = dists[i][k] + dists[k][j]\n    \n        #smallest number of neighbors\n        mn = n\n        city = None\n        for i in range(n):\n            cnt = len([j for j in dists[i] if j <= distanceThreshold])\n            if cnt <= mn:\n                mn = cnt\n                city = i\n        return city\n", "from typing import *\nfrom collections import defaultdict\nimport heapq\n\n\nclass BreakIt(Exception):\n    pass\n\n\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        G = self.construct_graph(edges)\n        # 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\n        smallest_neigh_count = float(\\\"inf\\\")\n        smallest_neigh_node = None\n        for i in range(n - 1, -1, -1):\n            valid_n = set()\n            q = []\n            heapq.heappush(q, (0, i))\n            visited = set()\n            shortest_distance_i = dict()\n            try:\n                while len(q) > 0:\n                    d, curr_n = heapq.heappop(q)\n                    visited.add(curr_n)\n                    for n, nd in G[curr_n]:\n                        old_d = self.relax_distance(shortest_distance_i, n, d + nd)\n                        found_shorter_path = old_d > d + nd\n                        if d + nd <= distanceThreshold and n != i:\n                            valid_n.add(n)\n                        if len(valid_n) >= smallest_neigh_count:\n                            raise BreakIt\n                        if n not in visited or found_shorter_path:\n                            heapq.heappush(q, (d + nd, n))\n                if len(valid_n) < smallest_neigh_count:\n                    smallest_neigh_count = len(valid_n)\n                    smallest_neigh_node = i\n            except BreakIt:\n                pass\n        return smallest_neigh_node\n\n    @staticmethod\n    def relax_distance(distance_map, d, dist):\n        curr_d = distance_map.get(d, float(\\\"inf\\\"))\n        if dist < curr_d:\n            distance_map[d] = dist\n        return curr_d\n\n    @staticmethod\n    def construct_graph(edges):\n        G = defaultdict(set)\n        for e in edges:\n            n1, n2, w = e\n            G[n1].add((n2, w))\n            G[n2].add((n1, w))\n        return G\n", "import itertools as it\n\n\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        inf = float(\\\"inf\\\")\n        dp = [[inf] * n for _ in range(n)]\n        \n        for i in range(n):\n            dp[i][i] = 0\n        \n        for a, b, w in edges:\n            dp[a][b] = min(dp[a][b], w)\n            dp[b][a] = min(dp[b][a], w)\n            \n        for k, j , i in it.permutations(range(n), 3):\n            if i < j:\n                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])\n                dp[j][i] = dp[i][j]\n            \n        out = min([(sum(1 for r in row if r <= distanceThreshold), -i) for i, row in enumerate(dp)])\n        \n        return -out[1]\n        ", "import collections\nimport sys\n\n\nclass Solution(object):\n    def findTheCity(self, n, edges, distanceThreshold):\n        \\\"\\\"\\\"\n        :type n: int\n        :type edges: List[List[int]]\n        :type distanceThreshold: int\n        :rtype: int\n        \\\"\\\"\\\"\n\n        total = sum([r[2] for r in edges])\n\n        if distanceThreshold >= total:\n            return n - 1\n\n        MAX_INT = 10001\n        dist = [[MAX_INT] * n for _ in range(n)]\n\n        for i in range(n):\n            dist[i][i] = 0\n\n        for i, j, d in edges:\n            dist[i][j] = dist[j][i] = d\n\n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    if dist[i][k] == MAX_INT or dist[k][j] == MAX_INT:\n                        continue\n\n                    if dist[i][j] > dist[i][k] + dist[k][j]:\n                        dist[i][j] = dist[i][k] + dist[k][j]\n\n        res = 0\n        min_cnt = n + 1\n\n        for i, row in enumerate(dist):\n            cnt = 0\n            for j in range(n):\n                if dist[i][j] <= distanceThreshold:\n                    cnt += 1\n\n                if cnt > min_cnt:\n                    break\n\n            if cnt <= min_cnt:\n                min_cnt = cnt\n                res = i\n\n        return res\n", "import sys\nfrom heapq import heappush, heappop\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n      def shortestPath(adj, V, src, k):\n        heap = []\n        dist = [sys.maxsize]*V\n        dist[src] = 0\n        \n        heappush(heap,(0,src))\n        \n        while heap:\n          u = heappop(heap)[1]\n          \n          for node in adj[u]:\n            v = node[0]\n            weight = node[1]\n            \n            if dist[v]>dist[u] + weight:\n              dist[v] = dist[u] + weight\n              heappush(heap, (dist[v],v))\n        \n        count = 0 \n        for d in dist:\n          if d<=k:\n            count+=1\n        \n        return count\n      \n      adj = collections.defaultdict(list)\n      \n      for val in edges:\n        adj[val[0]].append((val[1],val[2]))\n        adj[val[1]].append((val[0],val[2]))\n            \n      cities = [0]*n\n      \n      for i in range(n):\n        cities[i] = shortestPath(adj, n, i, distanceThreshold)\n      \n      minVal = cities[0]\n      minIndex = 0\n      \n      for i in range(1,n):\n        if cities[i]<=minVal:\n          minVal = cities[i]\n          minIndex = i\n            \n      return minIndex", "from collections import defaultdict\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], cap: int) -> int:\n        graph=defaultdict(list)\n        \n        for i in edges:\n            graph[i[0]].append([i[1],i[2]])\n            graph[i[1]].append([i[0],i[2]])\n            \n        # print(graph)\n        self.ans=-1\n        self.mi=float('inf')\n        def bfs(parent):\n            seen={parent:-1}\n            q=[(parent,0)]\n            while(q!=[]):\n                tem_node,used=q.pop(0)\n                for node,dist in graph[tem_node]:\n                    if((node not in seen or dist+used<seen[node]) and (dist+used)<=cap):\n                        q.append((node,dist+used))\n                        seen[node]=dist+used\n            if(self.mi>len(seen)):\n                self.mi=len(seen)\n                self.ans=parent\n            elif(self.mi==len(seen) and parent>self.ans):\n                self.ans=parent\n        \n        for i in range(n):\n            bfs(i)\n            \n        return self.ans\n        \n        \n        \n        \n        \n#         di=dict()\n#         for i in range(n):\n#             di[i]=set()\n        \n#         print(graph)\n#         # self.mi=float('inf')\n#         # self.node=-1\n#         def dfs(node,thres,covered,parent):\n#             if(thres<0):\n#                 return\n#             di[parent].add(node)\n#             for i in graph[node]:\n#                 dfs(i[0],thres-i[1],covered+1,parent)\n            \n        \n#         for i in range(n):\n#             dfs(i,distanceThreshold,0,i)\n#         ans=-1\n#         mi=float('inf')\n#         print(di)\n#         for i,j in di.items():\n#             if(len(j)-1<mi):\n#                 mi=len(j)-1\n#                 ans=i\n#             elif(len(j)-1==mi):\n#                 ans=i\n#         return ans\n        \n        \n        # return self.node\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \n        \n        tb = [[float('inf')] * n for _ in range(n)]\n        for i in range(n):\n            tb[i][i] = 0\n        \n        for f, t, c in edges:\n            tb[f][t] = tb[t][f] = c\n        \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    if i == j: continue\n                    if tb[i][k] + tb[k][j] < tb[i][j]:\n                        tb[i][j] = tb[i][k] + tb[k][j]\n                        \n        i = -1\n        c = n+1\n        for j in range(n):\n            cc = sum(1 for x in tb[j] if x <= distanceThreshold)\n            # print(j, cc)\n            if cc <= c:\n                i = j\n                c = cc\n        # print(tb)\n        return i", "'''\nUsing Dijkstra's Algorithm\n\nIdea:\n1) Do Dijkstra from every node due to the weights are non-negative\n2) For each city calculate the number of reachable cities within the threshold, then search for the optimal city.\n\n'''\nimport heapq\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \n        graph = defaultdict(list)\n        for u, v, w in edges:\n            graph[u].append((w,v))\n            graph[v].append((w,u))\n        \n        dist = [[float('inf')]*n for _ in range(n)]\n        minCities = n\n        ans = -1\n        \n        for i in range(n):\n            q = [(0,i)]\n            validCities = 0\n            \n            while q:\n                #print(q)\n                distance, node = heapq.heappop(q)\n                if distance < dist[i][node]:\n                    dist[i][node] = distance\n                    if distance <= distanceThreshold:\n                        validCities += 1\n                else:\n                    continue\n                \n                for neigh in graph[node]:\n                    if distance + neigh[0] < dist[i][neigh[1]]:\n                        heapq.heappush(q, (distance + neigh[0], neigh[1]))\n            \n            if validCities <= minCities:\n                minCities = validCities\n                ans = i\n            \n        #print(dist)\n        #print(ans)\n        return ans", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        G = [[] for _ in range(n)]\n        \n        for u, v, w in edges:\n            G[u].append((v, w))\n            G[v].append((u, w))\n        \n        cnt = [0]*n\n        \n        for i in range(n):\n            dist = [10**18]*n\n            dist[i] = 0\n            pq = [(dist[i], i)]\n            \n            while pq:\n                d, v = heappop(pq)\n                \n                if dist[v]<d:\n                    continue\n                    \n                for nv, w in G[v]:\n                    if dist[nv]>dist[v]+w:\n                        dist[nv] = dist[v]+w\n                        heappush(pq, (dist[nv], nv))\n            \n            for j in range(n):\n                if dist[j]<=distanceThreshold:\n                    cnt[i] += 1\n        \n        M = 10**18\n        \n        for i in range(n):\n            if M>=cnt[i]:\n                M = cnt[i]\n                ans = i\n        \n        return ans", "from collections import defaultdict\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], cap: int) -> int:\n        graph=defaultdict(list)\n        \n        for i in edges:\n            graph[i[0]].append([i[1],i[2]])\n            graph[i[1]].append([i[0],i[2]])\n            \n        print(graph)\n        self.ans=-1\n        self.mi=float('inf')\n        def bfs(parent):\n            seen={parent:-1}\n            q=[(parent,0)]\n            while(q!=[]):\n                tem_node,used=q.pop(0)\n                for node,dist in graph[tem_node]:\n                    if((node not in seen or dist+used<seen[node]) and (dist+used)<=cap):\n                        q.append((node,dist+used))\n                        seen[node]=dist+used\n            if(self.mi>len(seen)):\n                self.mi=len(seen)\n                self.ans=parent\n            elif(self.mi==len(seen) and parent>self.ans):\n                self.ans=parent\n        \n        for i in range(n):\n            bfs(i)\n            \n        return self.ans\n        \n        \n        \n        \n        \n#         di=dict()\n#         for i in range(n):\n#             di[i]=set()\n        \n#         print(graph)\n#         # self.mi=float('inf')\n#         # self.node=-1\n#         def dfs(node,thres,covered,parent):\n#             if(thres<0):\n#                 return\n#             di[parent].add(node)\n#             for i in graph[node]:\n#                 dfs(i[0],thres-i[1],covered+1,parent)\n            \n        \n#         for i in range(n):\n#             dfs(i,distanceThreshold,0,i)\n#         ans=-1\n#         mi=float('inf')\n#         print(di)\n#         for i,j in di.items():\n#             if(len(j)-1<mi):\n#                 mi=len(j)-1\n#                 ans=i\n#             elif(len(j)-1==mi):\n#                 ans=i\n#         return ans\n        \n        \n        # return self.node\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        MAX_VAL = 1e6 + 1\n        self.graph = [[MAX_VAL for _ in range(n)] for _ in range(n)]\n        for idx in range(n): self.graph[idx][idx] = 0\n        for edge in edges:\n            self.graph[edge[0]][edge[1]] = edge[2]\n            self.graph[edge[1]][edge[0]] = edge[2]\n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    if self.graph[i][k] + self.graph[k][j] < self.graph[i][j]:\n                        self.graph[i][j] = self.graph[i][k] + self.graph[k][j]\n        results = []\n        for idx in range(n):\n            results.append((idx, len([_ for _ in range(n) if self.graph[idx][_] <= distanceThreshold])))\n        return sorted(results, key=lambda x: (x[1], -x[0]))[0][0]", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        graph = collections.defaultdict(set)\n        for u, v, weight in edges:\n            graph[u].add((v, weight))\n            graph[v].add((u, weight))\n  \n        dic = {}\n        for num in range(n):\n            queue = [(num, 0)]\n            visited = {num:-1}\n            while queue:\n                node, total_weight = queue.pop(0)\n                for nei, weight in graph[node]:\n                    if total_weight + weight <= distanceThreshold and (nei not in visited or total_weight + weight < visited[nei]):\n                        queue.append((nei, total_weight + weight))\n                        visited[nei] = total_weight + weight\n                        \n            dic[num] = len(visited)\n            \n        return sorted(list(dic.items()), key = lambda x: (x[1], -x[0]))[0][0]\n", "from typing import List\nclass Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        city_dist_threshold = [float('inf')] * n\n        dist_matrix = []\n\n        for index in range(n):\n            dist_matrix.append([float('inf')] * n)\n\n        for i,j,weight in edges:\n            dist_matrix[i][j] = weight\n            dist_matrix[j][i] = weight\n        for i in range(n):\n            dist_matrix[i][i] = 0\n            \n        for k_index in range(n):\n            for i_index in range(n):\n                for j_index in range(n):\n                    if i_index == k_index or k_index == j_index or i_index == j_index:\n                        continue\n                    if dist_matrix[i_index][j_index] > dist_matrix[i_index][k_index] + dist_matrix[k_index][j_index]:\n                        dist_matrix[i_index][j_index] = dist_matrix[i_index][k_index] + dist_matrix[k_index][j_index]\n                    \n        for i_index in range(n):\n            for j_index in range(n):\n                if dist_matrix[i_index][j_index] <= distanceThreshold:\n                    if city_dist_threshold[i_index] == float('inf'):\n                        city_dist_threshold[i_index] = 0\n                    city_dist_threshold[i_index] += 1\n                    \n        min_cities, city = min(city_dist_threshold), None\n        for index in range(len(city_dist_threshold)):\n            if city_dist_threshold[index] == min_cities:\n                city = index\n        \n\n        return city", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        graph = collections.defaultdict(set)\n        for u, v, weight in edges:\n            graph[u].add((v, weight))\n            graph[v].add((u, weight))\n            \n        print(graph)\n        dic = {}\n        for num in range(n):\n            #print('num', num)\n            queue = [(num, 0)]\n            visited = {num:-1}\n            count = 0\n            while queue:\n                node, total_weight = queue.pop(0)\n                #print(node, total_weight)\n                for nei, weight in graph[node]:\n                    if total_weight + weight <= distanceThreshold and (nei not in visited or total_weight + weight < visited[nei]):\n                        count += 1\n                        queue.append((nei, total_weight + weight))\n                        visited[nei] = total_weight + weight\n                        \n            dic[num] = len(visited)\n        print(dic)\n        return sorted(list(dic.items()), key = lambda x: (x[1], -x[0]))[0][0]\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        graph = collections.defaultdict(dict)\n        \n        for i,j,d in edges:\n            graph[i][j] = graph[j][i] = d\n                   \n        def dikstra(node, distanceThreshold):\n            visited = [False]*n\n            dist = [float('inf')]*n\n            heap = [(0, node)]\n            \n            while not all(visited) and heap:\n                distance, node = heapq.heappop(heap)\n                if distance > distanceThreshold:\n                    break\n                    \n                dist[node] = distance\n                visited[node] = True\n                \n                for d in graph[node]:\n                    if not visited[d]:\n                        heapq.heappush(heap, (distance+graph[node][d], d))\n            \n            return len([i for i in dist if i<=distanceThreshold])\n        \n        \n        \n        res = 0\n        count = n\n        for i in range(n):\n            c = dikstra(i, distanceThreshold)\n            if c <= count:\n                res = max(res,i)\n                count = c\n        \n        return res\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        dis = [[float('inf')] * n for _ in range(n)]\n        for i, j, w in edges:\n            dis[i][j] = dis[j][i] = w\n        for i in range(n):\n            dis[i][i] = 0\n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])\n        res = {sum(d <= distanceThreshold for d in dis[i]): i for i in range(n)}\n        return res[min(res)]", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        #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\n        #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\n        graph = collections.defaultdict(list)\n        \n        for u, v, w in edges:\n            graph[u].append((v, w))\n            graph[v].append((u, w))\n            \n        def getNumberOfNeighbors(city):\n            heap = [(0, city)]\n            dist = {}\n            \n            while heap:\n                currW, u = heapq.heappop(heap)\n                if u in dist: #visited, skip it\n                    continue\n                if u != city:    \n                    dist[u] = currW\n                for v, w in graph[u]:\n                    if v in dist:\n                        continue\n                    if currW + w <= distanceThreshold: #find new reacheable city\n                        heapq.heappush(heap, (currW + w, v))\n            return len(dist)\n        \n        return max([(getNumberOfNeighbors(city), city) for city in range(n)], key=lambda x: (-x[0], x[1]))[-1]", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        distance = [[float('inf') for _ in range(n)] for _ in range(n)]\n        \n        for i, j, w in edges:\n            distance[i][j] = w\n            distance[j][i] = w\n        \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])\n        \n        m = collections.defaultdict()\n        ans = 0\n        \n        \n        for i in range(n):\n            temp = 0\n            for j in range(n):\n                if distance[i][j] <= distanceThreshold and i != j:\n                    temp += 1\n            m[temp] = i\n        return m[min(m.keys())]", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        graph = collections.defaultdict(list)\n        res = float('inf')\n        min_city = 0\n        for u, v, w in edges:\n            graph[u].append(( w, v))\n            graph[v].append((w, u))\n        def djikstra(node):\n            distance = {nid: float('inf') for nid in list(graph.keys())}\n            distance[node] = 0\n            heap = [(0, node)]\n            heapq.heapify(heap)\n            total = 0\n            while heap:\n                d, nd = heapq.heappop(heap)\n                if d > distance[nd]:\n                    continue\n                for nei in graph[nd]:\n                    nei_cost, nei_id = nei\n                    total = (d + nei_cost)\n                    if total < distance[nei_id]:\n                        distance[nei_id] = total\n                        heapq.heappush(heap, (total, nei_id))\n            return sum(dis <= distanceThreshold for dis in list(distance.values()))  - 1\n        #print(graph.keys())\n        res = {djikstra(i):i for i in range(n)}\n        return res[min(res)]\n        \n        \n                       \n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        connect = defaultdict(dict)\n        ansheap = []\n        for a,b,c in edges:\n            connect[a][b]=c\n            connect[b][a]=c\n        for i in range(n):\n            dist ={}\n            heap = [(0,i)]\n            while heap:\n                d, u = heapq.heappop(heap)\n                if d>distanceThreshold:\n                    break\n                if u not in dist:\n                    dist[u]=d\n                    for v in connect[u]:\n                        heapq.heappush(heap, (d+connect[u][v],v))\n            heapq.heappush(ansheap, (len(dist), -i))\n        return - ansheap[0][1]\n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        graph = [[] for _ in range(n)]\n        for i, j, w in edges:\n            graph[i].append((j, w))\n            graph[j].append((i, w))\n        \n        result = []\n        for i in range(n):\n            queue = [(0, i)]\n            visited = set()\n            while queue:\n                distance, i = heapq.heappop(queue)\n                if i in visited:\n                    continue\n                visited.add(i)\n                for j, w in graph[i]:\n                    if distance + w <= distanceThreshold:\n                        heapq.heappush(queue, (distance + w, j))\n            visited.remove(i)\n            result.append(list(visited))\n        return min(range(n), key=lambda x: (len(result[x]), -x))", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        distDict = defaultdict(dict)\n        citySet = set(list(range(n)))\n        visitedDict = defaultdict(dict)\n        stack = []\n        allEdge = 0\n        for a, b, w in edges:\n            distDict[a][b] = w\n            distDict[b][a] = w\n            allEdge += w\n            if a in citySet:\n                citySet.remove(a)\n                heapq.heappush(stack, (-distanceThreshold, a, a))\n                visitedDict[a][a] = distanceThreshold\n            if b in citySet:\n                citySet.remove(b)\n                heapq.heappush(stack, (-distanceThreshold, b, b))\n                visitedDict[b][b] = distanceThreshold\n        \n        if len(citySet) > 0:\n            return max(citySet)\n        \n        if distanceThreshold > allEdge:\n            return n-1\n        \n        while stack:\n            dLeft, source, curr = heapq.heappop(stack)\n            dLeft *= -1\n            # print(dLeft, source, curr)\n            for nextCity in distDict[curr]:\n                if (nextCity not in visitedDict[source] or visitedDict[source][nextCity] < (dLeft - distDict[curr][nextCity])) and distDict[curr][nextCity] <= dLeft:\n                    visitedDict[source][nextCity] = dLeft - distDict[curr][nextCity]\n                    heapq.heappush(stack, (-(dLeft - distDict[curr][nextCity]), source, nextCity))\n                # elif nextCity not in visitedDict[source] and distDict[curr][nextCity] == dLeft:\n                #     visitedDict[source].add(nextCity)\n        # print(visitedDict)\n        ansMax = float('inf')\n        ans = -1\n        for city in visitedDict:\n            if ansMax > len(visitedDict[city]):\n                ansMax = len(visitedDict[city])\n                ans = city\n            elif ansMax == len(visitedDict[city]):     \n                ans = max(ans, city)\n        return ans", "from math import floor\nfrom math import ceil\nfrom math import sqrt\nfrom collections import deque\nimport numpy\nfrom _collections import deque\n#from _ast import Num # LC doesn't like this\nfrom heapq import *\nfrom typing import List\nimport random\n\nMOD = int(1e9 + 7)\nBASE = 256\n\n\nclass Solution:\n\n    def findTheCity(self, n: int, edges: List[List[int]],\n                    distanceThreshold: int) -> int:\n        minD = [[-1 for i in range(n)] for i in range(n)]\n        for v in range(n):\n            minD[v][v] = 0\n        for e in edges:\n            u = e[0]\n            v = e[1]\n            w = e[2]\n            minD[u][v] = w\n            minD[v][u] = w\n\n        for midNode in range(n):\n            for u in range(n):\n                for v in range(n):\n                    fh = minD[u][midNode]\n                    sh = minD[midNode][v]\n                    if fh >= 0 and sh >= 0:\n                        if minD[u][v] < 0 or fh + sh < minD[u][v]:\n                            minD[u][v] = fh + sh\n        #print(minD)\n        ans = 0\n        minCnt = n + 1\n        for u in range(n):\n            cnt = 0\n            for v in range(n):\n                if minD[u][v] >= 0 and minD[u][v] <= distanceThreshold:\n                    cnt += 1\n        #   print(u, cnt)\n            if cnt <= minCnt:\n                minCnt = cnt\n                ans = u\n        return ans\n\n\\\"\\\"\\\"\nn = 4\nedges = [[0, 1, 3], [1, 2, 1], [1, 3, 4], [2, 3, 1]]\ndistanceThreshold = 4\nn = 5\nedges = [[0, 1, 2], [0, 4, 8], [1, 2, 3], [1, 4, 2], [2, 3, 1], [3, 4, 1]]\ndistanceThreshold = 2\ns = Solution()\nprint(s.findTheCity(n, edges, distanceThreshold))\n\\\"\\\"\\\"", "\\\"\\\"\\\"\n12:09\n\nfirst construct the graph\n\ngenerate shortest paths (within threshold) to each city from each city\nreturn the city with the smallest number of paths (and largest number for tiebreak)\n\niterate thru cities\n0\nkeep a PQ of the shortest distances to each node\nwhen we arrive at a new node, add the node + distance to queue\n0->1\n1: 2\n\n0->4\n4: 8\n\n1->2\n2: 3 + 2\n1->4\n4: min(8, 2 + 2) = 4\n\ncontinue until the queue is empty. O(E)\n\nat the end of the traversal, remove all nodes from the list of paths for which dist > threshold O(V)\n\ndo this for each vertex in the graph\nO((E + V)) * V)\n\nOutput: iterate through each list of cities, track min number of cities and choose the largest numbered city with the min.\n\n\\\"\\\"\\\"\nfrom collections import defaultdict, deque\nimport heapq\n\nclass Solution:\n    def construct_graph(self, n, edges, thresh):\n        graph = defaultdict(dict)\n        # Don't need to include the edge if it's greater than the threshold\n        for src, dst, weight in edges:\n            if weight <= thresh:\n                graph[src][dst] = weight\n                graph[dst][src] = weight\n        return graph\n    \n    def compute_distances(self, n, city, graph, thresh):\n        remain = set(range(n))\n        pq = [(city, 0)]\n        distances = [float('inf')] * n\n        distances[city] = 0\n        neighbors = []\n        \n        # Perform dijkstra's to every other city in the graph\n        while pq:\n            curr, dist = heapq.heappop(pq)\n            \n            # Update distances to neighbors\n            for adj, weight in graph[curr].items():\n                temp = weight + dist\n                if temp < distances[adj]:\n                    distances[adj] = temp\n                    heapq.heappush(pq, (adj, temp))\n        \n        # Return all nodes that are within the distance threshold\n        for neighbor, dist in enumerate(distances):\n            if neighbor != city and dist <= thresh:\n                neighbors.append(neighbor)\n                \n        return neighbors\n        \n            \n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        graph = self.construct_graph(n, edges, distanceThreshold)\n        neighbors = {}\n        \n        # Compute each city's distances to each neighboring city\n        for city in range(n):\n            neighbors[city] = self.compute_distances(n, city, graph, distanceThreshold)\n        \n        # print(graph, neighbors)\n        min_cities = len(neighbors[0])\n        correct_city = 0\n        \n        # Find the city with smallest number of neighbors\n        for city in range(1, n):\n            # print(min_cities, correct_city)\n            if len(neighbors[city]) <= min_cities:\n                min_cities = len(neighbors[city])\n                correct_city = city\n        \n        return correct_city\n        ", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        \n        G = collections.defaultdict(list)\n        \n        for e in edges:\n            G[e[0]].append((e[1],e[2]))\n            G[e[1]].append((e[0],e[2]))\n            \n        \n        def dfs(i):\n            dist = [math.inf]*n\n            dist[i]=0\n            Queue = collections.deque([(i,0)])\n            \n            while Queue:\n                j,d = Queue.popleft()\n                for k in G[j]:\n                    if d+k[1]<dist[k[0]] and d+k[1]<=distanceThreshold:\n                        dist[k[0]]=d+k[1]\n                        Queue.append((k[0],d+k[1]))\n            return sum(dist[i]<math.inf for i in range(n))-1\n        \n        nei = [(dfs(i),-i) for i in range(n)]\n        #print(nei)\n        heapq.heapify(nei)\n        ans = heapq.heappop(nei)\n        return -ans[1]\n        \n", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        #Ford-Faulkerson? Floyd?\n        \n        dis = [[float('inf')] * n for _ in range(n)]\n        \n        for i,j,w in edges:\n            dis[i][j] = w\n            dis[j][i] = w\n        \n        for i in range(0,n):\n            dis[i][i] = 0\n        \n        for k in range(0,n):\n            for i in range(0,n):\n                for j in range(0,n):\n                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])\n        \n        \n        nbs = [0]*n\n        \n        for i in range(0,n):\n            nbs[n-1-i] = len([j for j in dis[i] if 0 <j <= distanceThreshold])\n            \n        \n        \n        \n        return n-1 - nbs.index(min(nbs))", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        distances = [[sys.maxsize] * n for _ in range(n)]\n\n        for src,tar, dis in edges:\n            distances[src][tar]=dis\n            distances[tar][src]=dis\n\n        for i in range(n):\n            distances[i][i]=0\n\n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    distances[i][j]= min (distances[i][j], distances[i][k]+ distances[k][j])\n\n\n        counts={}\n        for i,each in enumerate(distances):\n            counts[len([e for e in each if e<=distanceThreshold])]= i\n\n        return counts[min(counts)]", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:\n        #graph init\n        maps =[[2**30] * n for _ in range(n)]\n        nums_neighbors = [0] * n\n        for i in range(n):\n            maps[i][i] = 0\n        for info in edges:\n            src, dst, cost = info\n            maps[src][dst] = cost\n            maps[dst][src] = cost\n            \n        for i in range(n):\n            for j in range(n):\n                for k in range(n):\n                    maps[j][k] = min(maps[j][k], maps[j][i] + maps[i][k])\n        \n        min_idx = 0\n        for i in range(n):\n            nums_neighbors[i] = len([x for x in maps[i] if x != 0 and x <= distanceThreshold])\n            if nums_neighbors[i] <= nums_neighbors[min_idx]:\n                min_idx = i\n        #print(maps)\n        #print(nums_neighbors)\n        return min_idx", "class Solution:\n    def findTheCity(self, n: int, edges: List[List[int]], dt: int) -> int:\n        dist = [[inf] * n for _ in range(n)]\n        \n        for f, t, c in edges:\n            dist[f][t] = min(dist[f][t], c)\n            dist[t][f] = min(dist[t][f], c)\n        \n        \n        for k in range(n):\n            for i in range(n):\n                for j in range(n):\n                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])\n        \n        arr = []\n        for i in range(n):\n            cnt = 0\n            for j in range(n):\n                if i == j or dist[i][j] > dt:\n                    continue\n                cnt += 1\n            arr.append((cnt, -i))\n        \n        arr.sort()\n        return -arr[0][1]"]