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.

Difficulty: interview

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])
                    else:
                        if 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

#
# @lc app=leetcode id=882 lang=python3
#
# [882] Reachable Nodes In Subdivided Graph
#
# https://leetcode.com/problems/reachable-nodes-in-subdivided-graph/description/
#
# algorithms
# Hard (40.58%)
# Likes:    161
# Dislikes: 139
# Total Accepted:    6.1K
# Total Submissions: 14.7K
# Testcase Example:  '[[0,1,10],[0,2,1],[1,2,2]]\
6\
3'
#
# 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 mMoves moves.
# 
# 
# 
# Example 1:
# 
# 
# Input: edges = [[0,1,10],[0,2,1],[1,2,2]], mMoves = 6, N = 3
# Output: 13
# Explanation: 
# The nodes that are reachable in the final graph after mMoves = 6 moves are
# indicated below.
# 
# 
# 
# 
# Example 2:
# 
# 
# Input: edges = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]], mMoves = 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 <= mMoves <= 10^9
# 1 <= N <= 3000
# A reachable node is a node that can be travelled to using at most mMoves moves
# starting from node 0.
# 
# 
# 
# 
# 
# 
#

class Solution:
    def reachableNodes(self, edges: List[List[int]], mMoves: int, N: int) -> int:
        \"\"\"
        :ref: https://leetcode.com/problems/reachable-nodes-in-subdivided-graph/discuss/156739/C%2B%2BJavaPython-Dijkstra-%2B-Priority-Queue
        \"\"\"
        graph = collections.defaultdict(dict)
        for i, j, lenInserted in edges: graph[i][j] = graph[j][i] = lenInserted
        maxHeap = [(-mMoves, 0)]
        seen = {}

        while maxHeap:
            negNumMoves, nodeIdx = heapq.heappop(maxHeap)
            if nodeIdx not in seen:
                seen[nodeIdx] = -negNumMoves
                for neighborIdx in graph[nodeIdx]:
                    nextNumMoves = -negNumMoves - graph[nodeIdx][neighborIdx] - 1
                    if neighborIdx not in seen and nextNumMoves >= 0:
                        heapq.heappush(maxHeap, (-nextNumMoves, neighborIdx))

        res = len(seen)
        for i, j, k in edges:
            res += min(seen.get(i, 0) + seen.get(j, 0), graph[i][j])
        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
        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 = collections.defaultdict(dict)
        for u, v, w in edges:
            g[u][v] = w
            g[v][u] = w
        q = [(0, 0, 0)]
        visited = [[10 ** 9 + 1, -1] for i in range(N)]
        visited[0] = [0, -1]
        while q:
            m, u, p = heapq.heappop(q)
            if m > visited[u][0]:
                continue
            for v, w in list(g[u].items()):
                if v == p:
                    continue
                mm = m + w + 1
                if mm <= M and mm < visited[v][0]:
                    visited[v][0] = mm
                    visited[v][1] = u
                    heapq.heappush(q, (mm, v, u))
        edges2 = set()
        edges3 = {}
        for u, (m, v) in enumerate(visited):
            if m > M:
                continue
            edges2.add((min(u, v), max(u, v)))
            for k, w in list(g[u].items()):
                if k == v:
                    continue
                t = (min(u, k), max(u, k))
                if m + w + 1 <= M:
                    edges2.add(t)
                else:
                    if t not in edges3:
                        edges3[t] = [0, 0]
                    if u < k:
                        edges3[t][0] = max(edges3[t][0], M - m)
                    else:
                        edges3[t][1] = max(edges3[t][1], M - m)
        result = 0
        nodes = set()
        for u, v in edges2:
            result += g[v].get(u, 0)
            nodes.add(u)
            nodes.add(v)
        result += len(nodes) - 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 = [[] 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
            # Each node is only visited once.  We've reached
            # a node in our original graph.
            ans += 1

            for nei, weight in list(graph[node].items()):
                # M - d is how much further we can walk from this node;
                # weight is how many new nodes there are on this edge.
                # v is the maximum utilization of this edge.
                v = min(weight, M - d)
                used[node, nei] = v

                # d2 is the total distance to reach 'nei' (neighbor) node
                # in the original graph.
                d2 = d + weight + 1
                if d2 < dist.get(nei, M+1):
                    heapq.heappush(pq, (d2, nei))
                    dist[nei] = d2

        # At the end, each edge (u, v, w) can be used with a maximum
        # of w new nodes: a max of used[u, v] nodes from one side,
        # and used[v, u] nodes from the other.
        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)
            # print(d, head)
            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:
        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 list(conns[n].items()):
                    if m in visited:
                        ans += min(M-d, conns[n][m])
                    else:
                        if 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:
        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)]          # (currently how many moves left, curr_node)
        moves_left = collections.defaultdict(int)
        
        while len(hq) > 0:
            curr_moves_left, curr_node = heappop(hq)  # 贪心就贪在这，每次pop出来的都是剩余步数最多（即离soure node最近）的node
            curr_moves_left = -curr_moves_left
            
            if curr_node in moves_left:     # if we have already reached this node with less steps, then just skip it
                continue
            moves_left[curr_node] = curr_moves_left
            
            for next_node, insert_cnt in graph[curr_node]:
                if insert_cnt >= curr_moves_left:   # we cannot reach the nextNode if there is not enough 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, dijkstra, heap, dist, used(u,v)=part of new nodes covered
        graph = defaultdict(dict)
        for u, v, w in edges:
            graph[u][v] = graph[v][u] = w # # of new nodes between u and v
        
        heap = [(0, 0)]
        dist = {0:0}
        used = dict() # key=(u,v) value=covered new nodes
        ans = 0 # final total num of nodes can be covered
        
        while heap:
            adist, anode = heapq.heappop(heap)
            if adist > dist[anode]: 
                continue
            
            ans += 1 # add one old node in the original graph
            
            for nei, weight in graph[anode].items():
                v = min(weight, M-adist) # source -> anode -> nei
                used[(anode, nei)] = v
                
                adist2 = adist + weight + 1 # cost of \"source -> anode -> nei\"
                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):
        # bfs, dijkstra 都有希望过
        # subdivisions = 细分！
        
        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:
        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 = [-10001] * N
        ans = 0
        while q:
            #print(list(q))
            hp, cur = heapq.heappop(q)
            if visited[cur] != -10001:
                #print(cur, visited[cur])
                continue
            hp = -hp
            visited[cur] = hp
            ans += 1
            for node, cost in g[cur]:
                nxt_hp = hp - cost - 1
                if nxt_hp < 0: continue
                heapq.heappush(q, (-nxt_hp, node))                    
        
        for i,j,n in edges:
            ui, uj = 0, 0
            if visited[i] != -10001: ui = visited[i]
            if visited[j] != -10001: 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,n in edges:
            g[i].append((j, n))
            g[j].append((i, n))
            
        q = [(-M, 0)]
        visited = [-10001] * N
        ans = 0
        while q:
            #print(list(q))
            hp, cur = heapq.heappop(q)
            if visited[cur] != -10001:
                #print(cur, visited[cur])
                continue
            hp = -hp
            visited[cur] = hp
            ans += 1
            for node, cost in g[cur]:
                nxt_hp = hp - cost - 1
                if nxt_hp >= 0: 
                    heapq.heappush(q, (-nxt_hp, node))                    
        
        for i,j,n in edges:
            ui, uj = 0, 0
            if visited[i] != -10001: ui = visited[i]
            if visited[j] != -10001: uj = visited[j]
            ans += min(ui+uj, n)
            
        return ans


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)
            # Count intermediate nodes reachable from either i, j
            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:
        
        #Create graph using dictioary of dictioary
        g=collections.defaultdict(dict)
        for edge in edges:
            g[edge[0]][edge[1]]=edge[2]+1
            g[edge[1]][edge[0]]=edge[2]+1
            
        #Use negative move to apply max-heap
        hq=[(-M,0)]*len(g[0])  #The move can be taken together for all outgoing edges
        
        if(len(hq)==0):  #There is no outgoing edges, it can visited minimum of 1
            return 1
        
        #Use the dictionary to store the max remaining moves at this node
        #This will make sure it will cover as many nodes as possible
        visited={}
        
        while hq:
            #Pop out the node with the highest remaining move
            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):  #make this move if it satisfies
                    #Don't update visited in this loop, becuase it can only be update after heappop
                    heapq.heappush(hq,(rem_move+weight,nei))

        #Count the number of nodes covered
        res=len(visited)
        
        counted=set()
        #Go through all edges 
        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)  #Avoid double couting the same edge
                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
    
        
        
        
        
        
            
            


class Solution(object):
    def reachableNodes(self, edges, M, N):
        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
            # Each node is only visited once.  We've reached
            # a node in our original graph.
            ans += 1

            for nei in graph[node]:
                weight=graph[node][nei]
                # M - d is how much further we can walk from this node;
                # weight is how many new nodes there are on this edge.
                # v is the maximum utilization of this edge.
                v = min(weight, M - d)
                used[node, nei] = v

                # d2 is the total distance to reach 'nei' (neighbor) node
                # in the original graph.
                d2 = d + weight + 1
                if d2 < dist.get(nei, M+1):
                    heapq.heappush(pq, (d2, nei))
                    dist[nei] = d2

        # At the end, each edge (u, v, w) can be used with a maximum
        # of w new nodes: a max of used[u, v] nodes from one side,
        # and used[v, u] nodes from the other.
        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:
        # Dijkstra's
        # Time  complexity: O(ElogN), where E is the length of edges.
        # Space complexity: O(N)
        graph = 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
            # Each node is only visited once.  We've reached
            # a node in our original graph.
            ans += 1

            for nei, weight in list(graph[node].items()):
                # M - d is how much further we can walk from this node;
                # weight is how many new nodes there are on this edge.
                # v is the maximum utilization of this edge.
                v = min(weight, M - d)
                used[node, nei] = v

                # d2 is the total distance to reach 'nei' (neighbor) node
                # in the original graph.
                d2 = d + weight + 1
                if d2 < dist.get(nei, M + 1):
                    heapq.heappush(pq, (d2, nei))
                    dist[nei] = d2

        # At the end, each edge (u, v, w) can be used with a maximum
        # of w new nodes: a max of used[u, v] nodes from one side,
        # and used[v, u] nodes from the other.
        for u, v, w in edges:
            ans += min(w, used.get((u, v), 0) + used.get((v, u), 0))

        return ans




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) # list (adj_vertex, edge_weight)
        for x, y, n in edges:
            adj[x].append([y, n + 1])
            adj[y].append([x, n + 1])
        q = PriorityQueue() # (dist, vertex)
        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) # (i, j): inner_nodes_visited, i < j
        q = [(0, 0)] # total_cost, node
        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())
        
        


class Solution:
    def reachableNodes(self, edges, M, N):
        \"\"\"
        :type edges: List[List[int]]
        :type M: int
        :type N: int
        :rtype: int
        \"\"\"
        adjacency = defaultdict(set)                    # map node to set of (nbor, number of nodes on edge)
        subdivisions = {}                               # map an edge to (number of nodes on edge, visited nodes)

        for a, b, intermediate in edges:
            subdivisions[(a, b)] = [intermediate, 0]
            subdivisions[(b, a)] = [intermediate, 0]
            adjacency[a].add((b, intermediate))
            adjacency[b].add((a, intermediate))

        queue = [(0, 0)]                                # (steps taken, node)
        visited = set()

        while queue and len(visited) < N:
            steps, node = heapq.heappop(queue)
            if node in visited:                         # already visited with lower or same steps
                continue
            visited.add(node)

            for nbor, distance in adjacency[node]:      # visit as many nodes as possible along this edge
                subdivisions[(node, nbor)][1] = min(distance, M - steps)

                if steps + distance + 1 <= M:           # visited all node on edge, add nbor to queue
                    heapq.heappush(queue, (steps + distance + 1, nbor))

        result = len(visited)                           # all nodes
        for (a, b), (distance, covered) in subdivisions.items():
            if a < b:
                result += min(distance, covered + subdivisions[(b, a)][1])  # sum edge nodes from both sides

        return result  
    
    
    def reachableNodes_(self, edges: List[List[int]], M: int, N: int) -> int:
        graph = collections.defaultdict(list)
        n = N 
        for i, j, ns in edges:
            if not ns:
                graph[i].append(j)
                graph[j].append(i)
                continue
            u = i
            v = n
            for _ in range(ns):
                graph[u].append(v)
                graph[v].append(u)
                u = v
                n += 1
                v = n
            v -= 1
            graph[v].append(j)
            graph[j].append(v)
        visited = {0}
        q = collections.deque([(0, 0)]) # node, move
        while q:
            for _ in range(len(q)):
                node, move = q.popleft()
                visited.add(node)
                if move == M:
                    continue
                for nxt in graph[node]:
                    if nxt not in visited:
                        q.append([nxt, move + 1])
        return len(visited)
                    
        
        

from collections import defaultdict, deque
import heapq

class Solution:
    def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
        outgoing = defaultdict(dict)
        
        # O(E)
        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]] # (dist_through_edge, src, dest)
        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 less than limit, we can travel along edge
            if dist_at_node < M:
                # the number of intermediate nodes already traveled on this edge
                t = traveled.get(src, {}).get(dest, 0)
                
                try_dest = False
                
                # if positive traveled, we've already hit this edge from this dir.
                # if zero, can travel up to full length of edge
                # if negative, have traveled this dist from other edge
                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


# 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   #用于记录i,j之间的edge上还剩多少未遍历的sub点
#         pq = [(0,0)]
#         seen = set() #利用了djikstra算法可以时我们对每个节点至遍历一次即可，故用seen记录
#         res = 0
#     #djikstra
#         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(object):
    def reachableNodes(self, edges, M, N):
        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
            # Each node is only visited once.  We've reached
            # a node in our original graph.
            ans += 1

            for nei, weight in graph[node].items():
                # M - d is how much further we can walk from this node;
                # weight is how many new nodes there are on this edge.
                # v is the maximum utilization of this edge.
                v = min(weight, M - d)
                used[node, nei] = v

                # d2 is the total distance to reach 'nei' (neighbor) node
                # in the original graph.
                d2 = d + weight + 1
                if d2 < dist.get(nei, M+1):
                    heapq.heappush(pq, (d2, nei))
                    dist[nei] = d2

        # At the end, each edge (u, v, w) can be used with a maximum
        # of w new nodes: a max of used[u, v] nodes from one side,
        # and used[v, u] nodes from the other.
        for u, v, w in edges:
            ans += min(w, used.get((u, v), 0) + used.get((v, u), 0))

        return ans

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(list)
        for x, y, n in edges:
            adj_list[x].append((y, n))
            adj_list[y].append((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 adj_list[cur]:
                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


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 *= -1
            visited[cur] = hp
            ans += 1
            for nxt, cost in g[cur]:
                nxt_hp = hp - cost - 1
                if visited[nxt] is not None or nxt_hp < 0:                     
                    continue                
                heapq.heappush(q, (-nxt_hp, nxt))
                
        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(n, (ui+uj))
        return ans


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
        # min queue for dijastra (distance from source, vertex)
        pq = [(0,0)]
        # weight used from u to v
        used = {}
        # min distance from source
        dist = {0: 0}
        res = 0
        
        while pq:
            d, v = heapq.heappop(pq)
            # dist in this path greater than previous route, no need to searching
            if d > dist[v]:
                continue
            # count this vertex
            res += 1
            
            for nei, weight in list(graph[v].items()):
                # insert how much weight/nodes can be used in edge v->nei
                use_wei = min(weight, M - d)
                used[v, nei] = use_wei
                
                # get min dis to next node
                d_min = d + weight + 1
                # if next node is not visited and distance smaller than M + 1
                # or has been visited but has greater distance from source
                # we can update distance and push new vertex to heap
                if d_min < dist.get(nei, M + 1):
                    dist[nei] = d_min
                    heapq.heappush(pq,(d_min, nei))
                    
        # insert traveled mid nodes to res
        for i, j, w in edges:
            res += min(w, used.get((i, j), 0) + used.get((j, i), 0))
        return res
                
            
                    


import math
from collections import defaultdict
from queue import PriorityQueue
class Solution:
    def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
        adj = defaultdict(list)
        for x, y, w in edges:
            adj[x].append([y, w + 1])
            adj[y].append([x, w + 1])
        dist = [math.inf for _ in range(N)]
        q = PriorityQueue() # queue of [dist, vertex_id]
        q.put([0, 0])
        dist[0] = 0
        while not q.empty():
            d, x = q.get()
            for y, w in adj[x]:
                if d + w <= M and dist[y] > d + w:
                    dist[y] = d + w
                    q.put([dist[y], y])
        cnt = len([1 for d in dist if d < math.inf])
        for x, y, w in edges:
            covered = 0
            if dist[x] < math.inf:
                covered += M - dist[x]
            if dist[y] < math.inf:
                covered += M - dist[y]
            cnt += min(w, covered)
        return cnt

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   #用于记录i,j之间的edge上还剩多少未遍历的sub点
        pq = [(0,0)]
        seen = set() #利用了djikstra算法可以时我们对每个节点至遍历一次即可，故用seen记录
        res = 0
    #djikstra
        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(object):
#     def reachableNodes(self, edges, M, N):
#         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
#             # Each node is only visited once.  We've reached
#             # a node in our original graph.
#             ans += 1

#             for nei, weight in graph[node].items():
#                 # M - d is how much further we can walk from this node;
#                 # weight is how many new nodes there are on this edge.
#                 # v is the maximum utilization of this edge.
#                 v = min(weight, M - d)
#                 used[node, nei] = v

#                 # d2 is the total distance to reach 'nei' (neighbor) node
#                 # in the original graph.
#                 d2 = d + weight + 1
#                 if d2 < dist.get(nei, M+1):
#                     heapq.heappush(pq, (d2, nei))
#                     dist[nei] = d2

#         # At the end, each edge (u, v, w) can be used with a maximum
#         # of w new nodes: a max of used[u, v] nodes from one side,
#         # and used[v, u] nodes from the other.
#         for u, v, w in edges:
#             ans += min(w, used.get((u, v), 0) + used.get((v, u), 0))

#         return ans


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:
    # O(Elog(E)) time, O(E) space
    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 __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))
                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 __init__(self):
        self.graph = defaultdict(list)
        self.visited = dict()
        self.new_touched = dict()
        self.new_vis_nodes_count = 0
    
    def dfs(self,v, M):
        
        self.visited[v]=M #0, 0_3_0, 0_3_1, 0_3_2,
        if M <= 0:
            return

        for u, w in self.graph[v]:
            self.new_touched[(v,u)]=max(min(w,M),self.new_touched.get((v,u),0))
            if u in self.visited and self.visited[u] >= M:
                continue
            if M>w:
                self.dfs(u, M-w-1)
    
    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 in self.visited and self.visited[u] <= v_dist+w+1:
                    continue
                
                if M>=v_dist+w+1:
                    heappush(nodes_queue,(v_dist+w+1,u))
                    
            
        #self.dfs(0,M)
        
        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
        
        # Dijkstra
        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) # Reachable big nodes
        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:
        # build graph (undirected)
        graph = defaultdict(list)
        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, w))

        
        # priority queue keep track of [(dist, node)]
        min_heap = [(0, 0)]
        min_dist = [M+1]*N
        min_dist[0] = 0
    
        # keep track of max utilization for edge u->v
        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]:
                # try to relax the child v
                used = min(M-dist, w)
                edge2used[(u, v)] = used
                # distance to reach child v from u
                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