Starting with an undirected graph (the "original graph") with nodes from 0 to N-1, subdivisions are made to some of the edges.
The graph is given as follows: edges[k] is a list of integer pairs (i, j, n) such that (i, j) is an edge of the original graph,
and n is the total number of new nodes on that edge. 
Then, the edge (i, j) is deleted from the original graph, n new nodes (x_1, x_2, ..., x_n) are added to the original graph,
and n+1 new edges (i, x_1), (x_1, x_2), (x_2, x_3), ..., (x_{n-1}, x_n), (x_n, j) are added to the original graph.
Now, you start at node 0 from the original graph, and in each move, you travel along one edge. 
Return how many nodes you can reach in at most M moves.
 
Example 1:
Input: edges = [[0,1,10],[0,2,1],[1,2,2]], M = 6, N = 3
Output: 13
Explanation: 
The nodes that are reachable in the final graph after M = 6 moves are indicated below.



Example 2:
Input: edges = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]], M = 10, N = 4
Output: 23
 

Note:

0 <= edges.length <= 10000
0 <= edges[i][0] < edges[i][1] < N
There does not exist any i != j for which edges[i][0] == edges[j][0] and edges[i][1] == edges[j][1].
The original graph has no parallel edges.
0 <= edges[i][2] <= 10000
0 <= M <= 10^9
1 <= N <= 3000
A reachable node is a node that can be travelled to using at most M moves starting from node 0.

Source: leetcode | Difficulty: MEDIUM
Tags: Graph algorithms

Data structures

Shortest paths

Starter code: class Solution:
    def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
        

Solutions:
class Solution:

	def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
		conns = defaultdict(dict)
		for (i, j, n) in edges:
			conns[i][j] = n
			conns[j][i] = n
		heap = [(0, 0)]
		visited = set()
		ans = 0
		while heap:
			(d, n) = heapq.heappop(heap)
			if n not in visited:
				visited.add(n)
				ans += 1
				for (m, inter) in conns[n].items():
					if m in visited:
						ans += min(M - d, conns[n][m])
					elif d + inter < M:
						heapq.heappush(heap, (d + inter + 1, m))
						ans += inter
						conns[m][n] = 0
					else:
						ans += M - d
						conns[m][n] -= M - d
		return ans


class Solution:

	def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
		g = collections.defaultdict(dict)
		for (u, v, w) in edges:
			g[u][v] = w
			g[v][u] = w
		q = [(0, 0)]
		visited = [10 ** 9 + 1 for i in range(N)]
		visited[0] = 0
		edges2 = set()
		edges3 = {}
		while q:
			(m, u) = heapq.heappop(q)
			if m > visited[u]:
				continue
			for (v, w) in list(g[u].items()):
				mm = m + w + 1
				t = (min(u, v), max(u, v))
				if mm <= M:
					edges2.add(t)
				else:
					if t not in edges3:
						edges3[t] = [0, 0]
					if u < v:
						edges3[t][0] = max(edges3[t][0], M - m)
					else:
						edges3[t][1] = max(edges3[t][1], M - m)
				if mm <= M and mm < visited[v]:
					visited[v] = mm
					heapq.heappush(q, (mm, v))
		result = 0
		nodes = set()
		for (u, v) in edges2:
			result += g[v].get(u, 0)
			nodes.add(u)
			nodes.add(v)
		result += len(nodes)
		if result == 0:
			result += 1
		for (k, v) in list(edges3.items()):
			if k in edges2:
				continue
			result += min(sum(v), g[k[0]][k[1]])
		return result


class Solution:

	def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
		g = collections.defaultdict(dict)
		for (s, e, v) in edges:
			g[s][e] = g[e][s] = v
		dist = {0: 0}
		pq = [(0, 0)]
		used = {}
		ans = 0
		while pq:
			(d, node) = heapq.heappop(pq)
			if d > dist[node]:
				continue
			ans += 1
			for (e, w) in g[node].items():
				v = min(w, M - d)
				used[node, e] = v
				d2 = d + w + 1
				if d2 < dist.get(e, M + 1):
					heapq.heappush(pq, (d2, e))
					dist[e] = d2
		for (s, e, w) in edges:
			ans += min(w, used.get((s, e), 0) + used.get((e, s), 0))
		return ans


class Solution:

	def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
		e = collections.defaultdict(dict)
		for (i, j, l) in edges:
			e[i][j] = e[j][i] = l
		pq = [(-M, 0)]
		seen = {}
		while pq:
			(moves, i) = heapq.heappop(pq)
			if i not in seen:
				seen[i] = -moves
				for j in e[i]:
					moves2 = -moves - e[i][j] - 1
					if j not in seen and moves2 >= 0:
						heapq.heappush(pq, (-moves2, j))
		res = len(seen)
		for (i, j, k) in edges:
			res += min(seen.get(i, 0) + seen.get(j, 0), e[i][j])
		return res


class Solution:

	def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
		graph = defaultdict(list)
		e2i = {}
		reach = {}
		res = 0
		heap = [(0, 0)]
		hm = {0: 0}
		for (i, (u, v, w)) in enumerate(edges):
			graph[u].append([v, w])
			graph[v].append([u, w])
			e2i[u, v] = i
			e2i[v, u] = i
			reach[i] = 0
		while heap:
			(moves, node) = heapq.heappop(heap)
			if moves > hm[node]:
				continue
			res += 1
			for (nei, cost) in graph[node]:
				idx = e2i[node, nei]
				reach[idx] = min(cost, reach[idx] + M - moves)
				h = moves + cost + 1
				if h < hm.get(nei, M + 1):
					hm[nei] = h
					heapq.heappush(heap, (h, nei))
		return res + sum(reach.values())


class Solution:

	def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
		g = [[] for _ in range(N)]
		for (i, j, n) in edges:
			g[i].append((j, n))
			g[j].append((i, n))
		q = [(-M, 0)]
		visited = [-sys.maxsize] * N
		ans = 0
		while q:
			(hp, cur) = heapq.heappop(q)
			if visited[cur] != -sys.maxsize:
				continue
			hp *= -1
			visited[cur] = hp
			ans += 1
			for (nxt, cost) in g[cur]:
				nxt_hp = hp - cost - 1
				if visited[nxt] != -sys.maxsize or nxt_hp < 0:
					continue
				heapq.heappush(q, (-nxt_hp, nxt))
		for (i, j, n) in edges:
			(ui, uj) = (0, 0)
			if visited[i] != -sys.maxsize:
				ui = visited[i]
			if visited[j] != -sys.maxsize:
				uj = visited[j]
			ans += min(n, ui + uj)
		return ans


class Solution:

	def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
		graph = collections.defaultdict(dict)
		for (u, v, w) in edges:
			graph[u][v] = graph[v][u] = w
		pq = [(0, 0)]
		dist = {0: 0}
		used = {}
		ans = 0
		while pq:
			(d, node) = heapq.heappop(pq)
			if d > dist[node]:
				continue
			ans += 1
			for (nei, weight) in list(graph[node].items()):
				v = min(weight, M - d)
				used[node, nei] = v
				d2 = d + weight + 1
				if d2 < dist.get(nei, M + 1):
					heapq.heappush(pq, (d2, nei))
					dist[nei] = d2
		for (u, v, w) in edges:
			ans += min(w, used.get((u, v), 0) + used.get((v, u), 0))
		return ans


from collections import defaultdict
import heapq

class Solution:

	def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
		g = defaultdict(dict)
		for (ii, jj, kk) in edges:
			g[ii][jj] = g[jj][ii] = kk
		(queue, flag) = ([(0, 0)], {0: 0})
		used = {}
		res = 0
		while queue:
			(d, head) = heapq.heappop(queue)
			if d > flag.get(head):
				continue
			res += 1
			for (kk, vv) in list(g[head].items()):
				v = min(vv, M - d)
				used[head, kk] = v
				now_d = d + vv + 1
				if now_d < flag.get(kk, M + 1):
					heapq.heappush(queue, (now_d, kk))
					flag[kk] = now_d
		for (ii, jj, kk) in edges:
			res += min(kk, used.get((ii, jj), 0) + used.get((jj, ii), 0))
		return res


class Solution:

	def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
		graph = collections.defaultdict(list)
		for (u, v, insert_cnt) in edges:
			graph[u].append((v, insert_cnt))
			graph[v].append((u, insert_cnt))
		hq = [(-M, 0)]
		moves_left = collections.defaultdict(int)
		while len(hq) > 0:
			(curr_moves_left, curr_node) = heappop(hq)
			curr_moves_left = -curr_moves_left
			if curr_node in moves_left:
				continue
			moves_left[curr_node] = curr_moves_left
			for (next_node, insert_cnt) in graph[curr_node]:
				if insert_cnt >= curr_moves_left:
					continue
				heappush(hq, (-(curr_moves_left - insert_cnt - 1), next_node))
		res = len(moves_left)
		for (u, v, insert_cnt) in edges:
			res += min(moves_left[u] + moves_left[v], insert_cnt)
		return res


class Solution:

	def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
		g = collections.defaultdict(dict)
		for (u, v, w) in edges:
			g[u][v] = w
			g[v][u] = w
		q = [(0, 0)]
		visited = [10 ** 9 + 1 for i in range(N)]
		visited[0] = 0
		result = 0
		edges2 = {}
		while q:
			(m, u) = heapq.heappop(q)
			if m > visited[u]:
				continue
			result += 1
			for (v, w) in list(g[u].items()):
				edge = (min(u, v), max(u, v))
				l = None
				if edge not in edges2:
					l = edges2[edge] = [0, 0]
				else:
					l = edges2[edge]
				i = 0 if u < v else 1
				l[i] = max(l[i], min(w, M - m))
				mm = m + w + 1
				if mm <= M and mm < visited[v]:
					visited[v] = mm
					heapq.heappush(q, (mm, v))
		for ((u, v), (l1, l2)) in list(edges2.items()):
			result += min(l1 + l2, g[u][v])
		return result


class Solution:

	def reachableNodes(self, edges, M, N):
		graph = defaultdict(dict)
		for (u, v, w) in edges:
			graph[u][v] = graph[v][u] = w
		heap = [(0, 0)]
		dist = {0: 0}
		used = dict()
		ans = 0
		while heap:
			(adist, anode) = heapq.heappop(heap)
			if adist > dist[anode]:
				continue
			ans += 1
			for (nei, weight) in graph[anode].items():
				v = min(weight, M - adist)
				used[anode, nei] = v
				adist2 = adist + weight + 1
				if adist2 < dist.get(nei, M + 1):
					dist[nei] = adist2
					heapq.heappush(heap, (adist2, nei))
		for (u, v, w) in edges:
			ans += min(w, used.get((u, v), 0) + used.get((v, u), 0))
		return ans

	def reachableNodes2(self, edges, M, N):
		graph = defaultdict(dict)
		for (u, v, w) in edges:
			graph[u][v] = graph[v][u] = w
		heap = [(0, 0)]
		dist = {0: 0}
		used = dict()
		ans = 0
		while heap:
			(adist, anode) = heapq.heappop(heap)
			if adist > dist[anode]:
				continue
			ans += 1
			for (nei, weight) in graph[anode].items():
				v = min(weight, M - adist)
				used[anode, nei] = v
				adist2 = adist + weight + 1
				if adist2 < dist.get(nei, M + 1):
					dist[nei] = adist2
					heapq.heappush(heap, (adist2, nei))
		for (u, v, weight) in edges:
			ans += min(weight, used.get((u, v), 0) + used.get((v, u), 0))
		return ans

	def reachableNodes1(self, edges, M, N):
		e = collections.defaultdict(dict)
		for (i, j, l) in edges:
			e[i][j] = e[j][i] = l
		pq = [(-M, 0)]
		seen = {}
		while pq:
			(moves, i) = heapq.heappop(pq)
			if i not in seen:
				seen[i] = -moves
				for j in e[i]:
					moves2 = -moves - e[i][j] - 1
					if j not in seen and moves2 >= 0:
						heapq.heappush(pq, (-moves2, j))
		res = len(seen)
		for (i, j, k) in edges:
			res += min(seen.get(i, 0) + seen.get(j, 0), e[i][j])
		return res


from heapq import heapify, heappop, heappush

class Solution:

	def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
		adj = {}
		for (i, j, n) in edges:
			for (n1, n2) in ((i, j), (j, i)):
				adj[n1] = adj.get(n1, {})
				adj[n1][n2] = n
		if 0 not in adj:
			return 1
		length = [M + 1 for _ in range(N)]
		visited = set([0])
		length[0] = 0
		closest = [(e + 1, 0, j) for (j, e) in list(adj[0].items())]
		heapify(closest)
		while closest:
			(l, frm, to) = heappop(closest)
			if l > M:
				break
			if to in visited:
				continue
			length[to] = length[frm] + adj[frm][to] + 1
			visited.add(to)
			for (to2, e) in list(adj.get(to, {}).items()):
				if to2 in visited:
					continue
				heappush(closest, (length[to] + e + 1, to, to2))
		reach = sum((l <= M for l in length))
		visited = set()
		for (i, l) in enumerate(length):
			visited.add(i)
			for (j, e) in list(adj.get(i, {}).items()):
				if j in visited:
					continue
				inter = max(min(2 * M - min(length[i], M) - min(length[j], M), e), 0)
				reach += inter
		return reach


class Solution:

	def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
		graph = collections.defaultdict(dict)
		for (u, v, d) in edges:
			graph[u][v] = graph[v][u] = d
		visited = collections.defaultdict(int)
		pq = [(-M, 0)]
		while len(pq) > 0:
			(moves, node) = heapq.heappop(pq)
			moves = -moves
			if node in visited and moves <= visited[node]:
				continue
			visited[node] = moves
			for (nxt, dis) in graph[node].items():
				if dis + 1 <= moves:
					nxt_moves = moves - dis - 1
					heappush(pq, (-nxt_moves, nxt))
		ret = sum((node in visited for node in range(N)))
		for (u, v, d) in edges:
			ret += min(visited[u] + visited[v], d)
		return ret


class Solution:

	def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
		g = collections.defaultdict(dict)
		for edge in edges:
			g[edge[0]][edge[1]] = edge[2] + 1
			g[edge[1]][edge[0]] = edge[2] + 1
		hq = [(-M, 0)] * len(g[0])
		if len(hq) == 0:
			return 1
		visited = {}
		while hq:
			(rem_move, node) = heapq.heappop(hq)
			if node in visited:
				continue
			visited[node] = rem_move
			for nei in list(g[node].keys()):
				weight = g[node][nei]
				if nei not in visited and rem_move + weight <= 0:
					heapq.heappush(hq, (rem_move + weight, nei))
		res = len(visited)
		counted = set()
		for edge in edges:
			edge_tuple = (min(edge[:2]), max(edge[:2]))
			if edge[0] in visited and edge[1] in visited and (edge_tuple not in counted):
				counted.add(edge_tuple)
				res += min(g[edge[0]][edge[1]] - 1, -(visited[edge[0]] + visited[edge[1]]))
			elif edge[0] in visited:
				res = res + -visited[edge[0]]
			elif edge[1] in visited:
				res = res + -visited[edge[1]]
		return res


from heapq import heappop, heappush
from collections import defaultdict

class Solution:

	def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
		graph = defaultdict(dict)
		for (i, j, l) in edges:
			graph[i][j] = graph[j][i] = l
		heap_queue = [(-M, 0)]
		seen = defaultdict(int)
		while heap_queue:
			(move, s) = heappop(heap_queue)
			if s in seen:
				continue
			seen[s] = -move
			for child in graph[s]:
				if child in seen:
					continue
				nxt_move = -move - graph[s][child] - 1
				if nxt_move >= 0:
					heappush(heap_queue, (-nxt_move, child))
		result = len(seen)
		for (i, j, l) in edges:
			result += min(seen.get(i, 0) + seen.get(j, 0), l)
		return result


from queue import PriorityQueue
import math
from collections import defaultdict

class Solution:

	def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
		adj = defaultdict(list)
		for (x, y, n) in edges:
			adj[x].append([y, n + 1])
			adj[y].append([x, n + 1])
		q = PriorityQueue()
		dist = [math.inf for _ in range(N)]
		dist[0] = 0
		q.put([0, 0])
		while not q.empty():
			(d, x) = q.get()
			for (y, w) in adj[x]:
				if d + w <= M and d + w < dist[y]:
					dist[y] = d + w
					q.put([dist[y], y])
		cnt = len([1 for d in dist if d < math.inf])
		for (x, y, n) in edges:
			c1 = M - dist[x] if dist[x] < math.inf else 0
			c2 = M - dist[y] if dist[y] < math.inf else 0
			cnt += min(n, c1 + c2)
		return cnt


class Solution:

	def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
		costs = defaultdict(dict)
		for (i, j, c) in edges:
			costs[i][j] = c
			costs[j][i] = c
		visited = set()
		spans = defaultdict(int)
		q = [(0, 0)]
		while q:
			(dist, a) = heapq.heappop(q)
			if a in visited:
				continue
			visited.add(a)
			cons = costs[a]
			for (b, cost) in list(cons.items()):
				if dist + cost + 1 <= M:
					heapq.heappush(q, (dist + cost + 1, b))
				spk = (min(a, b), max(a, b))
				spans[spk] = min(spans[spk] + M - dist, cost)
		return len(visited) + sum(spans.values())


from collections import defaultdict, deque
import heapq

class Solution:

	def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
		outgoing = defaultdict(dict)
		for (src, dest, n) in edges:
			outgoing[src][dest] = n
			outgoing[dest][src] = n
		traveled = defaultdict(dict)
		n_reached = 1
		visited = set([0])
		to_traverse = [(outgoing[0][dest], 0, dest) for dest in outgoing[0]]
		heapq.heapify(to_traverse)
		while len(to_traverse) > 0:
			(dist, src, dest) = heapq.heappop(to_traverse)
			inter = outgoing[src][dest]
			dist_at_node = dist - inter
			if dist_at_node < M:
				t = traveled.get(src, {}).get(dest, 0)
				try_dest = False
				if t == 0:
					dist_edge = min(M - dist_at_node, inter)
					if dist_edge == inter:
						traveled[src][dest] = inter
						traveled[dest][src] = inter
						try_dest = M - dist_at_node - inter > 0
					else:
						traveled[src][dest] = dist_edge
						traveled[dest][src] = -dist_edge
					n_reached += dist_edge
				elif t < 0:
					dist_edge = min(M - dist_at_node, inter + t)
					traveled[src][dest] = dist_edge
					n_reached += dist_edge
				if try_dest and dest not in visited:
					n_reached += 1
					visited.add(dest)
					for (next_dest, next_inter) in outgoing[dest].items():
						heapq.heappush(to_traverse, (dist_at_node + inter + 1 + next_inter, dest, next_dest))
		return n_reached


from collections import defaultdict, deque
import heapq

class Solution:

	def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
		d = defaultdict(set)
		for edge in edges:
			d[edge[0]].add((edge[1], edge[2] + 1))
			d[edge[1]].add((edge[0], edge[2] + 1))
		q = [(0, 0)]
		visited = defaultdict(lambda : float('inf'))
		visited[0] = 0
		sd = defaultdict(int)
		while len(q) > 0:
			(m, cur) = heapq.heappop(q)
			for (adj, dis) in d[cur]:
				if visited[adj] > m + dis and m + dis <= M:
					heapq.heappush(q, (m + dis, adj))
					visited[adj] = m + dis
				sd[cur, adj] = max(sd[cur, adj], min(dis - 1, M - m))
		ans = len([x for x in list(visited.values()) if x != float('inf')])
		for (a, b, c) in edges:
			ans += min(sd[a, b] + sd[b, a], c)
		return ans


class Solution:

	def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
		graph = {}
		for (u, v, w) in edges:
			graph.setdefault(u, {})
			graph[u][v] = w
			graph.setdefault(v, {})
			graph[v][u] = w
		q = []
		HP = {}
		q.append([0, M])
		while q:
			(cur_node, cur_hp) = q.pop(0)
			if cur_node in HP and HP[cur_node] > cur_hp:
				continue
			HP[cur_node] = cur_hp
			if cur_node in graph:
				for next_node in graph[cur_node]:
					weight = graph[cur_node][next_node]
					next_hp = cur_hp - weight - 1
					if next_hp < 0 or (next_node in HP and HP[next_node] > next_hp):
						continue
					q.append([next_node, next_hp])
		result = len(HP)
		for (u, v, w) in edges:
			uv = HP[u] if u in HP else 0
			vu = HP[v] if v in HP else 0
			result += min(uv + vu, w)
		return result


import heapq
import pprint
from collections import defaultdict, deque

class Solution:

	def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
		adj_list = defaultdict(dict)
		for (x, y, n) in edges:
			adj_list[x][y] = n
			adj_list[y][x] = n
		pq = [(0, 0)]
		visited_node = set()
		visited_edge = defaultdict(int)
		while pq:
			(d, cur) = heapq.heappop(pq)
			if d > M:
				break
			if cur in visited_node:
				continue
			visited_node.add(cur)
			for (nxt, n) in list(adj_list[cur].items()):
				visited_edge[cur, nxt] = max(visited_edge[cur, nxt], min(M - d, n + 1))
				heapq.heappush(pq, (d + n + 1, nxt))
		count_visited_edge = sum((min(visited_edge[x, y] + visited_edge[y, x], n) for (x, y, n) in edges))
		return len(visited_node) + count_visited_edge


class Solution:

	def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
		g = collections.defaultdict(dict)
		for edge in edges:
			(u, v, w) = edge
			g[u][v] = w
			g[v][u] = w
		pq = [(-M, 0)]
		HP = {}
		while pq:
			(hp, node) = heapq.heappop(pq)
			hp = -hp
			if node in HP:
				continue
			HP[node] = hp
			for child in g[node]:
				if child not in HP and hp - g[node][child] - 1 >= 0:
					heapq.heappush(pq, (-(hp - g[node][child] - 1), child))
		res = len(HP)
		for edge in edges:
			(u, v) = (edge[0], edge[1])
			uv = HP[u] if u in HP else 0
			vu = HP[v] if v in HP else 0
			res += min(edge[2], uv + vu)
		return res


from queue import PriorityQueue
from collections import defaultdict

class Solution:

	def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
		e_dict = defaultdict(dict)
		for (i, j, n) in edges:
			e_dict[i][j] = e_dict[j][i] = n
		seen = {}
		pq = PriorityQueue()
		pq.put((-M, 0))
		while pq.qsize() > 0:
			(remaining_moves, idx) = pq.get()
			if idx not in seen:
				seen[idx] = -remaining_moves
				for j in e_dict[idx]:
					j_remaining_moves = seen[idx] - e_dict[idx][j] - 1
					if j_remaining_moves >= 0 and j not in seen:
						pq.put((-j_remaining_moves, j))
		res = len(seen)
		for (i, j, k) in edges:
			res += min(seen.get(i, 0) + seen.get(j, 0), k)
		return res


class Solution:

	def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
		graph = collections.defaultdict(dict)
		for (u, v, w) in edges:
			graph[u][v] = graph[v][u] = w + 1
		heap = [(-M, 0)]
		d = {}
		while heap:
			(moves, u) = heapq.heappop(heap)
			if u not in d:
				d[u] = -moves
				for v in graph[u]:
					temp = -moves - graph[u][v]
					if v not in d and temp >= 0:
						heapq.heappush(heap, (-temp, v))
		res = len(d)
		for (u, v, w) in edges:
			res += min(d.get(u, 0) + d.get(v, 0), w)
		return res


class Solution:

	def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
		g = [[] for _ in range(N)]
		for (i, j, n) in edges:
			g[i].append((j, n))
			g[j].append((i, n))
		q = [(-M, 0)]
		visited = [None] * N
		ans = 0
		while q:
			(hp, cur) = heapq.heappop(q)
			if visited[cur] is not None:
				continue
			hp = -hp
			visited[cur] = hp
			ans += 1
			for (node, cost) in g[cur]:
				nxt_hp = hp - cost - 1
				if visited[node] is not None or nxt_hp < 0:
					continue
				heapq.heappush(q, (-nxt_hp, node))
		for (i, j, n) in edges:
			(ui, uj) = (0, 0)
			if visited[i] is not None:
				ui = visited[i]
			if visited[j] is not None:
				uj = visited[j]
			ans += min(ui + uj, n)
		return ans


class Solution:

	def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
		g = [[] for _ in range(N)]
		for (i, j, k) in edges:
			g[i].append((j, k))
			g[j].append((i, k))
		q = [(-M, 0)]
		HP = [-sys.maxsize] * N
		ans = 0
		while q:
			(hp, cur) = heapq.heappop(q)
			if HP[cur] != -sys.maxsize:
				continue
			hp *= -1
			HP[cur] = hp
			ans += 1
			for (nxt, nxt_hp) in g[cur]:
				nxt_hp = hp - nxt_hp - 1
				if nxt_hp < 0 or HP[nxt] != -sys.maxsize:
					continue
				heapq.heappush(q, (-nxt_hp, nxt))
		for (i, j, k) in edges:
			uv = 0 if HP[i] == -sys.maxsize else HP[i]
			vu = 0 if HP[j] == -sys.maxsize else HP[j]
			ans += min(k, uv + vu)
		return ans


import collections

class Solution:

	def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
		graph = collections.defaultdict(dict)
		for (i, j, w) in edges:
			graph[i][j] = graph[j][i] = w
		pq = [(0, 0)]
		used = {}
		dist = {0: 0}
		res = 0
		while pq:
			(d, v) = heapq.heappop(pq)
			if d > dist[v]:
				continue
			res += 1
			for (nei, weight) in list(graph[v].items()):
				use_wei = min(weight, M - d)
				used[v, nei] = use_wei
				d_min = d + weight + 1
				if d_min < dist.get(nei, M + 1):
					dist[nei] = d_min
					heapq.heappush(pq, (d_min, nei))
		for (i, j, w) in edges:
			res += min(w, used.get((i, j), 0) + used.get((j, i), 0))
		return res


class Solution:

	def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
		graph = [[] for _ in range(N)]
		remain = [[0] * N for _ in range(N)]
		for edge in edges:
			(i, j, t) = edge
			graph[i].append((j, t))
			graph[j].append((i, t))
			remain[i][j] = remain[j][i] = t
		pq = [(0, 0)]
		seen = set()
		res = 0
		while pq:
			(dist, node) = heapq.heappop(pq)
			if node in seen:
				continue
			res += 1
			seen.add(node)
			for (nei, d) in graph[node]:
				valid = min(M - dist, remain[node][nei])
				res += valid
				remain[node][nei] = remain[nei][node] = remain[nei][node] - valid
				cost_to_nei = dist + d + 1
				if cost_to_nei <= M and nei not in seen:
					heapq.heappush(pq, (cost_to_nei, nei))
		return res


class Solution:

	def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
		graph = defaultdict(dict)
		for (i, j, w) in edges:
			graph[i][j] = w
			graph[j][i] = w
		seen = set()
		edges_utilized = Counter()
		h = [(0, 0)]
		while h:
			(dist, node) = heapq.heappop(h)
			seen.add(node)
			for (nbr, w) in graph[node].items():
				if nbr not in seen and dist + w + 1 <= M:
					heapq.heappush(h, (dist + w + 1, nbr))
				edges_utilized[node, nbr] = max(edges_utilized[node, nbr], M - dist)
		count = len(seen)
		all_utilized_edges = edges_utilized.keys()
		edges_covered = set()
		for (fro, to) in all_utilized_edges:
			e = (min(fro, to), max(fro, to))
			if e in edges_covered:
				continue
			edges_covered.add(e)
			count += min(graph[fro][to], edges_utilized[fro, to] + edges_utilized[to, fro])
		return count


class Solution:

	def __init__(self):
		self.graph = defaultdict(list)
		self.visited = dict()
		self.new_touched = dict()
		self.new_vis_nodes_count = 0

	def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
		for (u, v, w) in edges:
			self.graph[u].append((v, w))
			self.graph[v].append((u, w))
		nodes_queue = [(0, 0)]
		self.visited[0] = 0
		while len(nodes_queue):
			(v_dist, v) = heappop(nodes_queue)
			self.visited[v] = v_dist
			for (u, w) in self.graph[v]:
				self.new_touched[v, u] = max(min(w, M - v_dist), self.new_touched.get((v, u), 0))
				if u not in self.visited and M >= v_dist + w + 1:
					heappush(nodes_queue, (v_dist + w + 1, u))
		res = len(list(self.visited.items()))
		for (u, v, w) in edges:
			res += min(w, self.new_touched.get((u, v), 0) + self.new_touched.get((v, u), 0))
		return res


class Solution:

	def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
		if M == 0:
			return 1
		graph = [[-1] * N for i in range(N)]
		nodes = set()
		for (i, j, n) in edges:
			graph[i][j] = n
			graph[j][i] = n
			nodes.add(i)
			nodes.add(j)
		visited = [False] * N
		q = [(-M, 0)]
		cost = 0
		count = 0
		while q:
			cur = heappop(q)
			if count == len(nodes) + 1:
				break
			if visited[cur[1]]:
				continue
			count += 1
			visited[cur[1]] = True
			steps = -cur[0]
			cost += 1
			if steps <= 0:
				continue
			for i in range(N):
				if graph[cur[1]][i] == -1:
					continue
				adj = (graph[cur[1]][i], i)
				if adj[0] + 1 > steps:
					cost += steps
					graph[cur[1]][i] -= steps
					graph[i][cur[1]] -= steps
				else:
					cost += adj[0]
					heappush(q, (-(steps - adj[0] - 1), adj[1]))
					graph[cur[1]][adj[1]] = -1
					graph[adj[1]][cur[1]] = -1
		return cost


import heapq

class Solution:

	def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
		graph = collections.defaultdict(dict)
		for (u, v, cost) in edges:
			graph[u][v] = graph[v][u] = cost
		pq = [(-M, 0)]
		seen = {}
		while pq:
			(moves, i) = heapq.heappop(pq)
			if i not in seen:
				seen[i] = -moves
				for j in graph[i]:
					rem_moves = -moves - graph[i][j] - 1
					if j not in seen and rem_moves >= 0:
						heapq.heappush(pq, (-rem_moves, j))
		res = len(seen)
		for (i, j, cost) in edges:
			res += min(seen.get(i, 0) + seen.get(j, 0), cost)
		return res


class Solution:

	def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
		graph = collections.defaultdict(list)
		for (u, v, w) in edges:
			graph[u].append((v, w))
			graph[v].append((u, w))
		hq = [(-M, 0)]
		hp = {}
		while hq:
			(m, node) = heapq.heappop(hq)
			if node in hp:
				continue
			m = -m
			hp[node] = m
			for (v, w) in graph[node]:
				if m > w:
					remains = m - w - 1
					heapq.heappush(hq, (-remains, v))
		ans = len(hp)
		for (u, v, w) in edges:
			a = hp[u] if u in hp else 0
			b = hp[v] if v in hp else 0
			if a + b < w:
				ans += a + b
			else:
				ans += w
		return ans


class Solution:

	def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
		graph = defaultdict(list)
		for (u, v, w) in edges:
			graph[u].append((v, w))
			graph[v].append((u, w))
		min_heap = [(0, 0)]
		min_dist = [M + 1] * N
		min_dist[0] = 0
		edge2used = defaultdict(int)
		res = 0
		while min_heap:
			(dist, u) = heapq.heappop(min_heap)
			if dist > min_dist[u]:
				continue
			res += 1
			for (v, w) in graph[u]:
				used = min(M - dist, w)
				edge2used[u, v] = used
				dist_v = dist + w + 1
				if dist_v < min_dist[v]:
					min_dist[v] = dist_v
					heapq.heappush(min_heap, (dist_v, v))
		for (u, v, w) in edges:
			res += min(w, edge2used[u, v] + edge2used[v, u])
		return res