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: MEDIUM
Tags: Dynamic programming

Graph algorithms

Shortest paths
Skill types: Dynamic programming

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

Solutions:
class Solution:

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


class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], limit: int) -> int:
		graph = collections.defaultdict(lambda : [])
		for (n1, n2, w) in edges:
			graph[n1].append((n2, w))
			graph[n2].append((n1, w))

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


class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		graph = {i: [] for i in range(n)}
		for (u, v, w) in edges:
			graph[u].append((v, w))
			graph[v].append((u, w))
		res = (0, math.inf)
		for i in range(n):
			visited = set()
			q = []
			heappush(q, (0, i))
			cities = 0
			while q:
				(current_weight, node) = heappop(q)
				if node in visited:
					continue
				visited.add(node)
				cities += 1
				for (neighbor, neighbor_weight) in graph[node]:
					if neighbor not in visited and current_weight + neighbor_weight <= distanceThreshold:
						heappush(q, (current_weight + neighbor_weight, neighbor))
			if cities - 1 <= res[1]:
				res = (i, cities - 1)
		return res[0]


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		dp = [[float('inf') for _ in range(n)] for _ in range(n)]
		for (s, e, w) in edges:
			dp[s][e] = w
			dp[e][s] = w
		for k in range(n):
			for i in range(n):
				for j in range(n):
					dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
		minlen = n
		res = -1
		for (i, row) in enumerate(dp):
			cnt = sum((v <= distanceThreshold and j != i for (j, v) in enumerate(row)))
			if cnt <= minlen:
				minlen = cnt
				res = i
		return res


class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		paths = []
		for i in range(n):
			paths.append([sys.maxsize] * n)
		for (src, dest, weight) in edges:
			paths[src][dest] = weight
			paths[dest][src] = weight
		for i in range(n):
			paths[i][i] = 0
		for k in range(n):
			for src in range(n):
				for dest in range(n):
					paths[src][dest] = min(paths[src][dest], paths[src][k] + paths[k][dest])
		globalNode = -1
		globalReachable = sys.maxsize
		for i in range(n):
			localNode = i
			localReachable = 0
			for j in range(n):
				if paths[i][j] <= distanceThreshold and j != i:
					localReachable += 1
			if localReachable < globalReachable:
				globalReachable = localReachable
				globalNode = localNode
			elif localReachable == globalReachable and localNode > globalNode:
				globalNode = localNode
		return globalNode


class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		d = [[float('inf') for _ in range(n)] for _ in range(n)]
		for (s, t, w) in edges:
			d[s][t] = w
			d[t][s] = w
		for i in range(n):
			for s in range(n):
				for t in range(n):
					d[s][t] = min(d[s][t], d[s][i] + d[i][t])
		neighbors = [0 for i in range(n)]
		for s in range(n):
			for t in range(n):
				if s != t and d[s][t] <= distanceThreshold:
					neighbors[s] += 1
		min_value = float('inf')
		res = None
		for v in range(n):
			if neighbors[v] <= min_value:
				min_value = neighbors[v]
				res = v
		return res


class Solution:

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


class Solution:

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

		def getNumberOfNeighbors(city):
			heap = [(0, city)]
			count = 0
			seen = set()
			while heap:
				(currW, u) = heapq.heappop(heap)
				if u in seen:
					continue
				seen.add(u)
				for (v, w) in graph[u]:
					if v in seen:
						continue
					if currW + w <= distanceThreshold:
						heapq.heappush(heap, (currW + w, v))
				count += 1
			return count
		for city in range(n):
			num = getNumberOfNeighbors(city)
			dist[num].append(city)
			self.min = min(self.min, num)
		return max(dist[self.min])


class Solution:

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


class Solution:

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


class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		dist = [[math.inf] * n for _ in range(n)]
		for (i, j, w) in edges:
			dist[i][j] = w
			dist[j][i] = w
		for i in range(n):
			dist[i][i] = 0
		for k in range(n):
			for i in range(n):
				for j in range(n):
					dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
		res = []
		for i in range(n):
			res.append(sum((dist[i][j] <= distanceThreshold for j in range(n))))
		print(res)
		tmp = (n, 0)
		for (i, c) in enumerate(res):
			if (c, -i) < tmp:
				tmp = (c, -i)
		return -tmp[1]


class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		dist = [[float('inf')] * n for _ in range(n)]
		for (i, j, w) in edges:
			dist[i][j] = w
			dist[j][i] = w
		for i in range(n):
			dist[i][i] = 0
		for k in range(n):
			for i in range(n):
				for j in range(n):
					dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
		res = 0
		minCnt = float('inf')
		for i in range(n):
			cnt = 0
			for d in dist[i]:
				if d <= distanceThreshold:
					cnt += 1
			if cnt <= minCnt:
				minCnt = cnt
				res = i
		return res


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

def floyedWarshalAllPairDist(graph):
	n = len(graph)
	for i in range(n):
		for j in range(n):
			for k in range(n):
				graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k])

class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		g = [[float('inf')] * n for _ in range(n)]
		for (u, v, w) in edges:
			g[u][v] = w
			g[v][u] = w
		for i in range(n):
			for u in range(n):
				for v in range(n):
					if u == v:
						g[u][v] = 0
					else:
						g[u][v] = min(g[u][v], g[u][i] + g[i][v])
		(city, count) = (-1, float('inf'))
		for i in range(n):
			tmp = sum((1 for x in g[i] if x <= distanceThreshold))
			if tmp <= count:
				city = i
				count = tmp
		return city


import sys

class Solution:

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


class Solution:

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

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


class Solution:

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


class Solution:

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


from collections import defaultdict

class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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

		def djikstra(node):
			distance = {nid: float('inf') for nid in list(graph.keys())}
			distance[node] = 0
			heap = [(0, node)]
			heapq.heapify(heap)
			total = 0
			while heap:
				(d, nd) = heapq.heappop(heap)
				if d > distance[nd]:
					continue
				for nei in graph[nd]:
					(nei_cost, nei_id) = nei
					total = d + nei_cost
					if total < distance[nei_id]:
						distance[nei_id] = total
						heapq.heappush(heap, (total, nei_id))
			return sum((dis <= distanceThreshold for dis in list(distance.values()))) - 1
		res = {djikstra(i): i for i in range(n)}
		return res[min(res)]


class Solution:

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


class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		matrix = [[float('inf') for x in range(n)] for y in range(n)]
		for i in range(n):
			matrix[i][i] = 0
		for (u, v, w) in edges:
			matrix[u][v] = w
			matrix[v][u] = w
		for k in range(n):
			for i in range(n):
				for j in range(n):
					matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])
		res = Counter()
		for (i, row) in enumerate(matrix):
			for (j, dist) in enumerate(row):
				if dist <= distanceThreshold and i != j:
					res[i] += 1
		best = 0
		for i in range(n):
			if res[i] <= res[best]:
				best = i
		return best
		unconnected = []
		i = 0
		while i < n:
			if res[i] == 0:
				unconnected.append(i)
			i += 1
		if len(unconnected) == 1:
			return unconnected[0]
		elif len(unconnected) > 1:
			return max(unconnected)
		ans = min(res.values())
		max_city = 0
		for city in range(len(res)):
			if res[city] <= ans and city > max_city:
				max_city = city
		return max_city


class Solution:

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


import heapq

class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		graph = []
		for _ in range(n):
			graph.append([float('inf')] * n)
		for (i, j, w) in edges:
			graph[i][j] = w
			graph[j][i] = w
		nums = []
		for i in range(n):
			ans = self.dijkstra(graph, i, distanceThreshold)
			nums.append(ans)
		ans = 0
		minW = float('inf')
		for (i, w) in enumerate(nums):
			if w <= minW:
				minW = w
				ans = i
		return ans

	def dijkstra(self, graph, idx, threshold):
		dist = [(w, i) for (i, w) in enumerate(graph[idx]) if w != float('inf')]
		heapq.heapify(dist)
		ans = []
		visited = {idx}
		while len(dist) > 0 and dist[0][0] <= threshold and (len(visited) <= len(graph)):
			(cur_w, i) = heapq.heappop(dist)
			if i not in visited:
				ans.append(i)
				visited.add(i)
				for (j, w) in enumerate(graph[i]):
					if w != float('inf'):
						heapq.heappush(dist, (w + cur_w, j))
		return len(ans)


class Solution:

	def dfs(self, q, D, V, k):
		Q = [q]
		V[q] = 0
		while Q:
			T = []
			for nd in Q:
				W = V[nd]
				for (n, w) in D[nd]:
					cl = W + w
					cr = V[n]
					if cl < cr and cl <= k:
						V[n] = cl
						T.append(n)
			Q = T
		return {a: b for (a, b) in V.items() if b != sys.maxsize}

	def findTheCity(self, N: int, E: List[List[int]], k: int) -> int:
		D = collections.defaultdict(list)
		for (f, t, w) in E:
			D[f].append((t, w))
			D[t].append((f, w))
		R = dict()
		mn = sys.maxsize
		for q in range(N):
			V = self.dfs(q, D, collections.defaultdict(lambda : sys.maxsize), k)
			R[q] = V
			if mn > len(V):
				mn = len(V)
		R = {a: b for (a, b) in R.items() if len(b) == mn}
		return max(R.keys())


import heapq

class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		distances = defaultdict(dict)
		edgeWeights = defaultdict(dict)
		for (start, end, weight) in edges:
			edgeWeights[start][end] = weight
			edgeWeights[end][start] = weight

		def computeDistances(i):
			iHeap = []
			heapq.heapify(iHeap)
			heapq.heappush(iHeap, (0, i))
			visited = set()
			while iHeap:
				(distance, vertex) = heapq.heappop(iHeap)
				if vertex in visited:
					continue
				if distance > distanceThreshold:
					break
				else:
					distances[i][vertex] = distance
					visited.add(vertex)
					for neighbor in edgeWeights[vertex]:
						if neighbor < i and i not in distances[neighbor]:
							continue
						edgeWeight = edgeWeights[vertex][neighbor]
						heapq.heappush(iHeap, (distance + edgeWeight, neighbor))
		lowestNumber = n
		lowestCity = -1
		for i in range(n):
			computeDistances(i)
			if len(distances[i]) <= lowestNumber:
				lowestNumber = len(distances[i])
				lowestCity = i
		return lowestCity


from typing import List

class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		city_dist_threshold = [float('inf')] * n
		dist_matrix = []
		for index in range(n):
			dist_matrix.append([float('inf')] * n)
		for i in range(n):
			dist_matrix[i][i] = 0
		for (i, j, weight) in edges:
			dist_matrix[i][j] = weight
			dist_matrix[j][i] = weight
		for k_index in range(n):
			for i_index in range(n):
				for j_index in range(n):
					dist_matrix[i_index][j_index] = min(dist_matrix[i_index][j_index], dist_matrix[i_index][k_index] + dist_matrix[k_index][j_index])
		for i_index in range(n):
			for j_index in range(n):
				if dist_matrix[i_index][j_index] <= distanceThreshold:
					if city_dist_threshold[i_index] == float('inf'):
						city_dist_threshold[i_index] = 0
					city_dist_threshold[i_index] += 1
		(min_cities, city) = (min(city_dist_threshold), None)
		for index in range(len(city_dist_threshold)):
			if city_dist_threshold[index] == min_cities:
				city = index
		return city


class Solution:

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


class Solution:

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

		def dijkstra(initial_node):
			dist = [float('inf')] * n
			dist[initial_node] = 0
			pq = [(initial_node, 0)]
			while pq:
				(node, d) = heappop(pq)
				for (adjnode, weight) in graph[node]:
					if dist[adjnode] > dist[node] + weight:
						dist[adjnode] = dist[node] + weight
						pq.append((adjnode, dist[node]))
			return dist
		city_num = 0
		cc = n + 1
		for node in range(n):
			dist = dijkstra(node)
			print(dist)
			c = -1
			for d in dist:
				if d <= threshold:
					c += 1
			if c <= cc:
				print(c)
				cc = c
				city_num = node
		return city_num


class Solution:

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


class Solution:

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


import collections
from heapq import heappop, heappush

class Solution:

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


class Solution:

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


from heapq import heappush, heappop

class Solution:

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


class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		minDistance = collections.defaultdict(lambda : collections.defaultdict(lambda : math.inf))
		for i in range(n):
			minDistance[i][i] = 0
		for (u, v, weight) in edges:
			minDistance[u][v] = weight
			minDistance[v][u] = weight
		for k in range(n):
			for i in range(n):
				for j in range(n):
					minDistance[i][j] = min(minDistance[i][j], minDistance[i][k] + minDistance[k][j])
		minNeighborCount = math.inf
		minCity = -1
		for i in range(n):
			neighborCount = sum((minDistance[i][j] <= distanceThreshold for j in range(n) if j != i))
			if neighborCount <= minNeighborCount:
				minNeighborCount = neighborCount
				minCity = i
		return minCity


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], threeshold: int) -> int:

		class Graph:

			def __init__(self, vertices):
				self.v = vertices
				self.graph = collections.defaultdict(dict)

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

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


class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		edges_dict = collections.defaultdict(list)
		for (src, dest, weight) in edges:
			edges_dict[src].append((dest, weight))
			edges_dict[dest].append((src, weight))
		import heapq

		def get_reachable_count(nd, distance):
			heap = [(0, nd)]
			count = 0
			visited = set()
			while heap:
				(travelled, nd) = heapq.heappop(heap)
				if nd in visited:
					continue
				visited.add(nd)
				count += 1
				for (dest, new_dist) in edges_dict[nd]:
					if new_dist + travelled > distance or dest in visited:
						continue
					heapq.heappush(heap, (new_dist + travelled, dest))
			return count - 1
		get_reachable_count(1, distanceThreshold)
		curr_min_val = float('inf')
		curr_best_idx = -1
		for i in range(n):
			count = get_reachable_count(i, distanceThreshold)
			if count <= curr_min_val:
				(curr_min_val, curr_best_idx) = (count, i)
		return curr_best_idx


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


from heapq import heappush, heappop

class Solution:

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

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


class Solution:

	def visitedAllNodes(self, src, graph, n, max_d):
		visited = [False for i in range(n)]
		heap = [(0, src)]
		while heap:
			(d, node) = heapq.heappop(heap)
			if not visited[node]:
				visited[node] = True
				for (neighbor, w) in graph[node]:
					if d + w <= max_d and (not visited[neighbor]):
						heapq.heappush(heap, (d + w, neighbor))
		return sum(visited)

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		graph = collections.defaultdict(list)
		(node, nodes_reached) = (-1, n + 1)
		for (i, j, w) in edges:
			graph[i].append((j, w))
			graph[j].append((i, w))
		for i in range(n):
			count = self.visitedAllNodes(i, graph, n, distanceThreshold)
			if count <= nodes_reached:
				node = i
				nodes_reached = count
		return node


class Solution:

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


import heapq

class Solution:

	def shortestPath(self, root, graph, distanceThreshold):
		dist = {}
		dist[root] = 0
		visited = set()
		queue = [(0, root)]
		count = 0
		while queue:
			(pickDist, pick) = heapq.heappop(queue)
			if pick in visited:
				continue
			visited.add(pick)
			if pickDist <= distanceThreshold:
				count += 1
			else:
				continue
			for (neighbor, weight) in graph[pick]:
				dist[neighbor] = min(dist.get(neighbor, float('inf')), pickDist + weight)
				heapq.heappush(queue, (dist[neighbor], neighbor))
		return count

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		graph = {k: [] for k in range(n)}
		for (u, v, w) in edges:
			graph[u].append((v, w))
			graph[v].append((u, w))
		minReachableCount = float('inf')
		ans = 0
		for i in range(n):
			reachCount = self.shortestPath(i, graph, distanceThreshold)
			if reachCount <= minReachableCount:
				minReachableCount = reachCount
				ans = i
		return ans


from collections import defaultdict
import heapq

class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		results = []
		graph = defaultdict(dict)
		for (x, y, dist) in edges:
			graph[x][y] = dist
			graph[y][x] = dist
		for i in range(n):
			results.append(self.traverse(graph, distanceThreshold, i, n))
		min_result = min(results)
		for i in range(n - 1, -1, -1):
			if results[i] == min_result:
				return i
		return

	def traverse(self, graph, threshold, start, n):
		q = [[start, 0]]
		count = 0
		distances = [float('inf')] * n
		distances[start] = 0
		while q:
			(city, dist) = heapq.heappop(q)
			for key in list(graph[city].keys()):
				new_dist = dist + graph[city][key]
				if distances[key] > new_dist:
					distances[key] = new_dist
					heapq.heappush(q, [key, dist + graph[city][key]])
		count = sum([1 for x in distances if x <= threshold])
		return count - 1


class Solution:

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


class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		dp = [[float(inf)] * n for _ in range(n)]
		for (a, b, cost) in edges:
			dp[a][b] = cost
			dp[b][a] = cost
		for i in range(n):
			dp[i][i] = 0
		for k in range(n):
			for i in range(n):
				for j in range(n):
					dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
		idx = 0
		m = len([e for e in dp[0] if e <= distanceThreshold])
		for i in range(1, n):
			l = len([e for e in dp[i] if e <= distanceThreshold])
			if l <= m:
				m = l
				idx = i
		return idx


class Solution:

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


from heapq import *

class Solution:

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

		def find_n_neigh(source_city):
			visited = set()
			pq = [(0, source_city)]
			while pq:
				(trav_dist, curr_city) = heappop(pq)
				if curr_city in visited:
					continue
				if curr_city != source_city:
					visited.add(curr_city)
				for (neigh, distance) in graph[curr_city]:
					if neigh not in visited and trav_dist + distance <= distanceThreshold:
						heappush(pq, (trav_dist + distance, neigh))
			return len(visited)
		graph = defaultdict(list)
		for (city, neigh, distance) in edges:
			graph[city].append((neigh, distance))
			graph[neigh].append((city, distance))
		n_neighs = [find_n_neigh(city) for city in range(n)]
		min_n = min(n_neighs)
		return [city for city in range(n) if n_neighs[city] == min_n][-1]


class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		graph = defaultdict(list)
		result = {}
		for edge in edges:
			src = edge[0]
			dest = edge[1]
			cost = edge[2]
			graph[src].append((dest, cost))
			graph[dest].append((src, cost))
		for i in range(n):
			num_vertices = self.get_num_vertices_less_than_threshold(graph, i, distanceThreshold)
			result[i] = num_vertices
		min_vertex_val = min(result.values())
		index = list([-1 if x[1] != min_vertex_val else x[0] for x in list(result.items())])
		return max(index)

	def get_num_vertices_less_than_threshold(self, graph, vertex, thresh):
		queue = []
		queue.append((0, vertex))
		reachable_nodes = []
		while queue:
			(dist, node) = heapq.heappop(queue)
			if node in reachable_nodes:
				continue
			reachable_nodes.append(node)
			for vert in graph[node]:
				neigh_vert = vert[0]
				neigh_cost = vert[1]
				if dist + neigh_cost <= thresh:
					heapq.heappush(queue, (dist + neigh_cost, neigh_vert))
		return len(reachable_nodes) - 1


class Solution:

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


import gc
from collections import defaultdict
gc.disable()

class Solution:

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


class Solution:

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

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


class Solution:

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


from collections import defaultdict
from collections import deque

class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		n2n = defaultdict(list)
		for (x, y, w) in edges:
			n2n[x].append([y, w])
			n2n[y].append([x, w])
		minds = [[-1] * n for _ in range(n)]
		for i in range(n):
			minds[i][i] = 0
		for (x, y, d) in edges:
			minds[x][y] = d
			minds[y][x] = d
		for source in range(n):
			visited = [0] * n
			q = deque()
			q.append(source)
			visited[source] = 1
			while q:
				node = q.popleft()
				for (next_node, d) in n2n.get(node, []):
					if not visited[next_node]:
						q.append(next_node)
						visited[next_node] = 1
						if minds[source][next_node] == -1 or minds[source][next_node] > minds[source][node] + d:
							minds[source][next_node] = minds[source][node] + d
					elif minds[source][next_node] == -1 or minds[source][next_node] > minds[source][node] + d:
						minds[source][next_node] = minds[source][node] + d
						q.append(next_node)
		min_reach = n
		max_node = 0
		for source in range(n):
			reach_count = 0
			for mind in minds[source]:
				if mind != -1 and mind <= distanceThreshold:
					reach_count += 1
			if reach_count <= min_reach:
				max_node = source
				min_reach = reach_count
		return max_node


class Solution:

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


from heapq import *

class Solution:

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

		def find_n_neighbours(source_city):
			visited = set()
			heap = [(0, source_city)]
			while heap:
				(travelled_distance, curr_city) = heappop(heap)
				if curr_city in visited:
					continue
				if curr_city != source_city:
					visited.add(curr_city)
				for (neigh, distance) in graph[curr_city]:
					if neigh in visited:
						continue
					if travelled_distance + distance <= distanceThreshold:
						heappush(heap, (travelled_distance + distance, neigh))
			return len(visited)
		graph = defaultdict(list)
		for (from_, to, distance) in edges:
			graph[from_].append((to, distance))
			graph[to].append((from_, distance))
		neighbours = [find_n_neighbours(i) for i in range(n)]
		min_count = min(neighbours)
		sel_cities = [i for i in range(n) if neighbours[i] == min_count]
		return sel_cities[-1]


class Solution:

	def bfs(self, graph, src, num_nodes, threshold):
		d = [float('inf')] * num_nodes
		q = []
		q.append(src)
		d[src] = 0
		while len(q) > 0:
			u = q.pop(0)
			for v in graph[u]:
				if d[v[0]] > d[u] + v[1]:
					d[v[0]] = d[u] + v[1]
					q.append(v[0])
		return len([i for (i, x) in enumerate(d) if x <= threshold and x != 0])

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		graph = collections.defaultdict(list)
		for e in edges:
			graph[e[0]].append([e[1], e[2]])
			graph[e[1]].append([e[0], e[2]])
		min_val = float('inf')
		node = -1
		for i in range(n):
			r = self.bfs(graph, i, n, distanceThreshold)
			if r <= min_val:
				node = i
				min_val = r
		return node


class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		dist = [[float('inf')] * n for _ in range(n)]
		for (u, v, w) in edges:
			dist[u][v] = w
			dist[v][u] = w
		for k in range(n):
			for i in range(n):
				for j in range(n):
					if i == j:
						continue
					dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
		mn = n + 1
		output = None
		for start in range(n):
			count = len([d for d in dist[start] if d <= distanceThreshold])
			if count <= mn:
				mn = count
				output = start
		return output


class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		oe = {}
		for (l, r, w) in edges:
			if l not in oe:
				oe[l] = set()
			if r not in oe:
				oe[r] = set()
			oe[l].add((r, w))
			oe[r].add((l, w))

		def dks(been, c, t):
			cw = been[c]
			if c not in oe:
				return
			pending = set()
			for (other, weight) in oe[c]:
				ow = weight + cw
				if ow > distanceThreshold:
					continue
				if other not in been:
					been[other] = ow
					pending.add(other)
					continue
				if been[other] > ow:
					been[other] = ow
					pending.add(other)
			for o in pending:
				dks(been, o, t)
		smallest = 0
		mc = n + 1
		for city in range(n):
			dv = {city: 0}
			dks(dv, city, distanceThreshold)
			cities = len(list(dv.keys())) - 1
			if cities <= mc:
				smallest = city
				mc = cities
		return smallest


class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		adj = collections.defaultdict(dict)
		for (a, b, c) in edges:
			adj[a][b] = adj[b][a] = c

		def bfs(s, distanceThreshold):
			visited = [False] * n
			dist = [float('inf')] * n
			frontier = [(0, s)]
			while frontier:
				(d, s) = heapq.heappop(frontier)
				if d > distanceThreshold:
					break
				dist[s] = d
				visited[s] = True
				for t in adj[s]:
					if not visited[t]:
						heapq.heappush(frontier, (d + adj[s][t], t))
			return len([d for d in dist if d <= distanceThreshold])
		res = 0
		count = n
		for i in range(n):
			c = bfs(i, distanceThreshold)
			if c <= count:
				res = max(res, i)
				count = c
		return res


import numpy as np

class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		dist = np.inf * np.ones((n, n))
		for k in range(len(edges)):
			dist[edges[k][0], edges[k][1]] = edges[k][2]
			dist[edges[k][1], edges[k][0]] = edges[k][2]
		for k in range(n):
			dist[k, k] = 0
		for k in range(n):
			for i in range(n):
				for j in range(n):
					if dist[i, j] > dist[i, k] + dist[j, k]:
						dist[i, j] = dist[i, k] + dist[j, k]
		dist[dist > distanceThreshold] = 0
		dist[dist > 0] = 1
		number = np.sum(dist, 1)
		curr_min = n
		index = 0
		for k in range(n):
			if number[k] <= curr_min:
				curr_min = number[k]
				index = k
		return index


class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		g = collections.defaultdict(dict)
		for (i, j, w) in edges:
			g[i][j] = w
			g[j][i] = w
		t = distanceThreshold

		def dist(u):
			q = [(0, u)]
			ret = {}
			while q:
				(d, v) = heapq.heappop(q)
				if v in ret:
					continue
				ret[v] = d
				for k in g[v]:
					if k not in ret and d + g[v][k] <= t:
						heapq.heappush(q, (d + g[v][k], k))
			return len(ret)
		ans = None
		num = n + 1
		for i in range(n):
			c = dist(i)
			if c <= num:
				num = c
				ans = i
		return ans


class Solution:

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


class Solution:

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

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


class Solution:

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

		def dijk(i, budget):
			(seen, pq) = (set(), [(0, i, 0)])
			while pq:
				(cost, u, steps) = heapq.heappop(pq)
				seen.add(u)
				for (nei, weight) in graph[u]:
					if nei in seen or cost + weight > budget:
						continue
					else:
						heapq.heappush(pq, (cost + weight, nei, steps + 1))
			return len(seen)
		(min_city, ans) = (n, None)
		for i in range(n):
			n_reachable = dijk(i, distanceThreshold)
			if n_reachable <= min_city:
				(min_city, ans) = (n_reachable, i)
		return ans


class Solution:

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


import heapq

class Solution:

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

		def djikstras(edges, cities, src):
			matrix = {}
			for edge in edges:
				if edge[0] not in matrix:
					matrix[edge[0]] = []
				matrix[edge[0]].append((edge[1], edge[2]))
				if edge[1] not in matrix:
					matrix[edge[1]] = []
				matrix[edge[1]].append((edge[0], edge[2]))
			vertices = []
			visited = []
			heapq.heappush(vertices, (0, src))
			while vertices:
				(vertexDist, vertex) = heapq.heappop(vertices)
				if vertex in visited:
					continue
				visited.append(vertex)
				if vertexDist <= distanceThreshold:
					cities.append(vertex)
					if vertex in matrix:
						for (v, w) in matrix[vertex]:
							newDist = vertexDist + w
							heapq.heappush(vertices, (newDist, v))
			return cities
		cityList = []
		finalCityList = []
		for i in range(n):
			cities = djikstras(edges, [], i)
			if cities:
				heapq.heappush(cityList, (len(cities), i * -1))
		return heapq.heappop(cityList)[1] * -1


class Solution:

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

		def bfs(i):
			q = [(0, i)]
			visited = {i}
			while q:
				(w, j) = heapq.heappop(q)
				visited.add(j)
				for (k, w_) in g[j]:
					if k not in visited and w + w_ <= distanceThreshold:
						heapq.heappush(q, (w + w_, k))
			return visited
		return -min([(len(bfs(i)), -i) for i in range(n)])[1]


class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		dp = [n * [float('inf')] for _ in range(n)]
		for (f, t, w) in edges:
			dp[f][t] = dp[t][f] = w
		for k in range(n):
			for i in range(n):
				for j in range(n):
					dp[i][j] = min(dp[i][k] + dp[k][j], dp[i][j])
		res = -1
		minv = float('inf')
		for i in range(n):
			count = 0
			for j in range(n):
				if i != j and dp[i][j] <= distanceThreshold:
					count += 1
			if count <= minv:
				minv = count
				res = i
		return res


class Solution:

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

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


class Solution:

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

		def dijk(i, budget):
			(seen, pq) = (set(), [(0, i, 0)])
			while pq:
				(cost, u, steps) = heapq.heappop(pq)
				seen.add(u)
				for (nei, weight) in graph[u]:
					if nei in seen or cost + weight > budget:
						continue
					heapq.heappush(pq, (cost + weight, nei, steps + 1))
			return len(seen)
		(min_city, ans) = (n, None)
		for i in range(n):
			n_reachable = dijk(i, distanceThreshold)
			if n_reachable <= min_city:
				(min_city, ans) = (n_reachable, i)
		return ans


class Solution:

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

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


import numpy as np

class Solution:

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


import sys

class Solution:

	def constructGraph(self, edges, n):
		graph = [[sys.maxsize for i in range(n)] for j in range(n)]
		for (i, j, k) in edges:
			graph[i][j] = k
			graph[j][i] = k
		return graph

	def floydWarshall(self, graph, n):
		for k in range(n):
			for i in range(n):
				for j in range(n):
					if i == j:
						graph[i][j] = 0
					graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
					graph[j][i] = graph[i][j]

	def getCitiesUnderThreshold(self, graph, distanceThreshold, n):
		arr = [None for i in range(n)]
		for i in range(n):
			lis = []
			for j in range(n):
				if graph[i][j] <= distanceThreshold and graph[i][j] != 0:
					lis.append(j)
			arr[i] = lis
		return arr

	def cityWithLeastNumber(self, arr):
		minNum = sys.maxsize
		for (i, j) in enumerate(arr):
			if len(j) <= minNum:
				minNum = len(j)
				curr = i
		return curr

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		graph = self.constructGraph(edges, n)
		self.floydWarshall(graph, n)
		arr = self.getCitiesUnderThreshold(graph, distanceThreshold, n)
		curr = self.cityWithLeastNumber(arr)
		return curr


class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		L = [[[float('inf') for i in range(n + 1)] for j in range(n)] for k in range(n)]
		for (u, v, w) in edges:
			L[u][v][0] = w
			L[v][u][0] = w
		for k in range(1, n + 1):
			for i in range(n):
				for j in range(n):
					if j == i:
						continue
					L[i][j][k] = min(L[i][j][k - 1], L[i][k - 1][k - 1] + L[k - 1][j][k - 1])
		min_ct = float('inf')
		minval = n - 1
		for i in range(n - 1, -1, -1):
			ct = 0
			for j in range(n):
				if i == j:
					continue
				if L[i][j][n] <= distanceThreshold:
					ct += 1
			if ct < min_ct:
				min_ct = ct
				minval = i
		return minval


import heapq
from collections import defaultdict

class Solution:

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

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


class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		import collections
		graph = collections.defaultdict(list)
		for (u, v, w) in edges:
			graph[u].append((v, w))
			graph[v].append((u, w))
		print([(self.getNumberOfNeighbors(city, graph, distanceThreshold), city) for city in range(n)])
		print(max([(self.getNumberOfNeighbors(city, graph, distanceThreshold), city) for city in range(n)]))
		print(max([(self.getNumberOfNeighbors(city, graph, distanceThreshold), city) for city in range(n)], key=lambda x: (-x[0], x[1])))
		return max([(self.getNumberOfNeighbors(city, graph, distanceThreshold), city) for city in range(n)], key=lambda x: (-x[0], x[1]))[-1]

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


class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		g = {}
		for (u, v, w) in edges:
			if u in g:
				g[u].append((v, w))
			else:
				g[u] = [(v, w)]
			if v in g:
				g[v].append((u, w))
			else:
				g[v] = [(u, w)]

		def numOfNb(city):
			minheap = [(0, city)]
			dist = {}
			while minheap:
				(currw, u) = heapq.heappop(minheap)
				if u != city:
					dist[u] = currw
				if u not in g:
					continue
				for (v, w) in g[u]:
					if v in dist:
						continue
					if currw + w <= distanceThreshold:
						heapq.heappush(minheap, (currw + w, v))
			return len(dist)
		ans = 0
		minnb = n
		for i in range(n):
			nb = numOfNb(i)
			if nb <= minnb:
				minnb = nb
				ans = i
		return ans


from collections import defaultdict

class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		dist = defaultdict(list)
		for (x, y, w) in edges:
			dist[x].append((y, w))
			dist[y].append((x, w))
		(curmin_idx, curmin_val) = (None, None)

		def dfs(idx, visited, threshold):
			if threshold < 0:
				return
			visited[idx] = threshold
			for (iidx, weight) in dist[idx]:
				if threshold - weight > visited[iidx]:
					dfs(iidx, visited, threshold - weight)
		for i in range(n):
			visited = [-1] * n
			dfs(i, visited, distanceThreshold)
			cur_visited = sum((1 for v in visited if v >= 0))
			if curmin_val is None or cur_visited <= curmin_val:
				curmin_val = cur_visited
				curmin_idx = i
		return curmin_idx


class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], d: int) -> int:
		if n == 2:
			return 1
		graph = {x: [] for x in range(n)}
		for edge in edges:
			graph[edge[0]].append((edge[1], edge[2]))
			graph[edge[1]].append((edge[0], edge[2]))

		def reachable(node, visited, threshold, dist):
			for nei in graph[node]:
				if dist + nei[1] < visited[nei[0]] and dist + nei[1] <= threshold:
					visited[nei[0]] = dist + nei[1]
					reachable(nei[0], visited, threshold, dist + nei[1])
		res = 0
		temp = n
		for i in reversed(list(range(n))):
			visited = [float('inf') for _ in range(n)]
			visited[i] = 0
			c = 0
			dist = 0
			for nei in graph[i]:
				if dist + nei[1] < visited[nei[0]] and dist + nei[1] <= d:
					visited[nei[0]] = dist + nei[1]
					reachable(nei[0], visited, d, dist + nei[1])
			for val in visited:
				if val > 0 and val != float('inf'):
					c += 1
			if c < temp:
				res = i
				temp = c
		return res


class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		adj = [[] for i in range(n)]
		res = [0 for i in range(n)]
		ans = float('inf')
		city = -1
		for i in edges:
			(a, b, c) = i
			adj[a].append((b, c))
			adj[b].append((a, c))
		for i in range(n):
			visited = [float('inf') for j in range(n)]
			visited[i] = 0
			traverse(i, visited, distanceThreshold, 0, adj)
			res[i] = n - visited.count(float('inf'))
		for i in range(n):
			if res[i] <= ans:
				ans = res[i]
				city = i
		return city

def traverse(curr, visited, threshold, dist, adj):
	if dist > threshold:
		return
	visited[curr] = dist
	for pair in adj[curr]:
		(city, next_dist) = pair
		if dist + next_dist <= visited[city]:
			traverse(city, visited, threshold, dist + next_dist, adj)


class Solution:

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


class Solution:

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

	def neighbours(self, i):
		heap = [(0, i)]
		d = {}
		while heap:
			(distance, node) = heappop(heap)
			if node in d:
				continue
			if node != i:
				d[node] = distance
			for (nei, w) in self.dict1[node]:
				if nei in d:
					continue
				if distance + w <= self.distanceThreshold:
					heappush(heap, (distance + w, nei))
		return len(d)


class Solution:

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

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


from collections import defaultdict
from heapq import heapify, heappush, heappop
import math

class Solution:

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


class Solution:

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


from collections import defaultdict

class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		graph = defaultdict(dict)
		for (city1, city2, weight) in edges:
			graph[city1][city2] = weight
			graph[city2][city1] = weight
		(res, res_reachable) = (None, float('inf'))
		for i in range(n):
			visited = set()
			unvisited = set()
			shortest_distance = [float('inf')] * n
			for j in range(n):
				if j == i:
					visited.add(j)
					shortest_distance[i] = 0
				else:
					unvisited.add(j)
			cur = i
			reachable = defaultdict(set)
			while cur != None:
				for neighbor in graph[cur]:
					if neighbor not in visited:
						if shortest_distance[cur] + graph[cur][neighbor] <= distanceThreshold:
							reachable[i].add(neighbor)
							if shortest_distance[cur] + graph[cur][neighbor] < shortest_distance[neighbor]:
								shortest_distance[neighbor] = shortest_distance[cur] + graph[cur][neighbor]
				cur = None
				for city in unvisited:
					if shortest_distance[city] != float('inf'):
						if cur == None:
							cur = city
						elif shortest_distance[city] < shortest_distance[cur]:
							cur = city
				if cur != None:
					visited.add(cur)
					unvisited.remove(cur)
			if len(reachable[i]) <= res_reachable:
				res_reachable = len(reachable[i])
				res = i
		return res


class Solution:

	def dijkstra(self, graph, src):
		(dist, visited) = ({}, collections.defaultdict(bool, {src: True}))
		for u in graph:
			dist[u] = float('inf')
		dist[src] = 0
		heap = [(0, src)]
		while heap:
			(cur, city) = heapq.heappop(heap)
			visited[city] = True
			for (to, weight) in graph[city]:
				if not visited[to] and dist[to] > cur + weight:
					dist[to] = cur + weight
					heapq.heappush(heap, (dist[to], to))
		return dist

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		graph = collections.defaultdict(list)
		for (u, v, w) in edges:
			graph[u].append((v, w))
			graph[v].append((u, w))
		neighbors = collections.defaultdict(int)
		for city in graph:
			for (c, dist) in list(self.dijkstra(graph, src=city).items()):
				if city != c and dist <= distanceThreshold:
					neighbors[city] += 1
		for i in range(n):
			if neighbors[i]:
				pass
		(answer, min_neighbors) = (-1, float('inf'))
		for (city, num) in list(neighbors.items()):
			if num < min_neighbors or (num == min_neighbors and city > answer):
				answer = city
				min_neighbors = num
		return answer


class Solution:

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


class Solution:

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


def floydWarshall(adj, n):
	for k in range(n):
		for i in range(n):
			for j in range(n):
				stopOver = adj[i][k] + adj[k][j]
				if stopOver < adj[i][j]:
					adj[i][j] = stopOver

class Solution:

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


class Solution:

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


class Solution:

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

		def find_num_closest(city):
			visited = set()
			q = [(0, city)]
			while q:
				(dist, c) = heappop(q)
				if c in visited:
					continue
				visited.add(c)
				for (weight, dest) in graph[c]:
					if dist + weight <= threshold:
						heappush(q, (dist + weight, dest))
			return len(visited)
		min_val = float('inf')
		min_city = None
		for i in range(n):
			closest = find_num_closest(i)
			if closest <= min_val:
				min_val = closest
				min_city = i
		return min_city


class Solution:

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


class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], D: int) -> int:
		dists = [[inf for _ in range(n)] for _ in range(n)]
		for (a, b, w) in edges:
			dists[a][b] = dists[b][a] = w
		for i in range(n):
			dists[i][i] = 0
		for k in range(n):
			for i in range(n):
				for j in range(n):
					if dists[i][k] + dists[k][j] < dists[i][j]:
						dists[i][j] = dists[j][i] = dists[i][k] + dists[k][j]
		return min(list(range(n)), key=lambda i: (sum((int(d <= D) for d in dists[i])), -i))


class Solution:

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

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

			def dijkstrase(s):
				queue = [(0, s)]
				seen = {s: 0}
				while queue:
					(w, s) = heapq.heappop(queue)
					for (nei, dw) in graph[s]:
						if nei not in seen or w + dw < seen[nei]:
							seen[nei] = w + dw
							heapq.heappush(queue, (w + dw, nei))
				return seen
			distances = [dijkstrase(i) for i in range(n)]
			ans = []
			for i in range(n):
				total = 0
				for (k, v) in list(distances[i].items()):
					if 0 < v <= distanceThreshold:
						total += 1
				ans.append(total)
			return max([i for i in range(n) if ans[i] == min(ans)])
		return method1()


class Solution:

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


class Solution:

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


class Solution:

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

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


from collections import defaultdict

class Solution:

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


import heapq

class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		dist = [[float('inf')] * n for _ in range(n)]
		graph = defaultdict(list)
		for (u, v, w) in edges:
			dist[u][v] = w
			dist[v][u] = w
			dist[u][u] = 0
			dist[v][v]
		minCities = n
		ans = -1
		for k in range(n):
			for i in range(n):
				numCities = 0
				for j in range(n):
					if dist[i][j] > dist[i][k] + dist[k][j]:
						dist[i][j] = dist[i][k] + dist[k][j]
					if k == n - 1:
						if dist[i][j] <= distanceThreshold:
							numCities += 1
				if k == n - 1:
					if numCities <= minCities:
						ans = i
						minCities = numCities
		return ans


class Solution:

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


class Solution:

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


class Solution:

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

		def find_cities_k(vertex, vis):
			q = []
			heapq.heappush(q, [0, vertex])
			while q:
				(dis, node) = heapq.heappop(q)
				if node in vis:
					continue
				vis.add(node)
				if dis <= distanceThreshold:
					if vertex != node:
						count[vertex] += 1
				for (w, neigh) in graph[node]:
					if neigh not in vis:
						heapq.heappush(q, [dis + w, neigh])
		for i in range(n):
			find_cities_k(i, set())
		min_ = 10000
		city_ = -1
		for i in range(n):
			if count[i] <= min_:
				min_ = count[i]
				city_ = i
		return city_


class Solution:

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


class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		dists = [[distanceThreshold + 1 for i in range(n)] for j in range(n)]
		for (s, e, w) in edges:
			dists[s][e] = w
			dists[e][s] = w
		for i in range(n):
			dists[i][i] = 0
		for k in range(n):
			for i in range(n):
				for j in range(n):
					if dists[i][k] + dists[k][j] > distanceThreshold:
						continue
					elif dists[i][j] is None:
						dists[i][j] = dists[i][k] + dists[k][j]
					elif dists[i][k] + dists[k][j] < dists[i][j]:
						dists[i][j] = dists[i][k] + dists[k][j]
		mn = n
		city = None
		for i in range(n):
			cnt = len([j for j in dists[i] if j <= distanceThreshold])
			if cnt <= mn:
				mn = cnt
				city = i
		return city


import sys
from heapq import heappush, heappop

class Solution:

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

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


from collections import defaultdict

class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], cap: int) -> int:
		graph = defaultdict(list)
		for i in edges:
			graph[i[0]].append([i[1], i[2]])
			graph[i[1]].append([i[0], i[2]])
		self.ans = -1
		self.mi = float('inf')

		def bfs(parent):
			seen = {parent: -1}
			q = [(parent, 0)]
			while q != []:
				(tem_node, used) = q.pop(0)
				for (node, dist) in graph[tem_node]:
					if (node not in seen or dist + used < seen[node]) and dist + used <= cap:
						q.append((node, dist + used))
						seen[node] = dist + used
			if self.mi > len(seen):
				self.mi = len(seen)
				self.ans = parent
			elif self.mi == len(seen) and parent > self.ans:
				self.ans = parent
		for i in range(n):
			bfs(i)
		return self.ans


class Solution:

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


import heapq

class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		graph = collections.defaultdict(dict)
		for (i, j, d) in edges:
			graph[i][j] = graph[j][i] = d

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


class Solution:

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


class Solution:

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


class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		G = collections.defaultdict(list)
		for e in edges:
			G[e[0]].append((e[1], e[2]))
			G[e[1]].append((e[0], e[2]))

		def dfs(i):
			dist = [math.inf] * n
			dist[i] = 0
			Queue = collections.deque([(i, 0)])
			while Queue:
				(j, d) = Queue.popleft()
				for k in G[j]:
					if d + k[1] < dist[k[0]] and d + k[1] <= distanceThreshold:
						dist[k[0]] = d + k[1]
						Queue.append((k[0], d + k[1]))
			return sum((dist[i] < math.inf for i in range(n))) - 1
		nei = [(dfs(i), -i) for i in range(n)]
		heapq.heapify(nei)
		ans = heapq.heappop(nei)
		return -ans[1]


class Solution:

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


class Solution:

	def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
		distances = [[sys.maxsize] * n for _ in range(n)]
		for (src, tar, dis) in edges:
			distances[src][tar] = dis
			distances[tar][src] = dis
		for i in range(n):
			distances[i][i] = 0
		for k in range(n):
			for i in range(n):
				for j in range(n):
					distances[i][j] = min(distances[i][j], distances[i][k] + distances[k][j])
		counts = {}
		for (i, each) in enumerate(distances):
			counts[len([e for e in each if e <= distanceThreshold])] = i
		return counts[min(counts)]


class Solution:

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


class Solution:

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