INF = float('inf')

class Solution:
    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:
        eg = defaultdict(list)
        for u, v, c in edges:
            eg[u].append((v, c))
            eg[v].append((u, c))
        distance = [INF] * n
        distance[0] = 0

        q = [(0, 0)]  # distance, node
        while q:
            cur_dist, cur_node = heappop(q)
            if cur_dist > distance[cur_node]:
                continue
            for neigh_node, edge_cnt in eg[cur_node]:
                neigh_dist = cur_dist + (edge_cnt + 1)
                if not (neigh_dist < distance[neigh_node]):
                    continue
                distance[neigh_node] = neigh_dist
                heappush(q, (neigh_dist, neigh_node))

        ans = 0
        for i in range(n):
            if distance[i] <= maxMoves:
                ans += 1

        for u, v, c in edges:
            from_u = max(0, maxMoves - distance[u])
            from_v = max(0, maxMoves - distance[v])
            ans += min(c, from_u + from_v)

        return ans