def reachable_nodes_brute_force(edges, max_moves, number_of_nodes):
    reachable_nodes = {0}
    queue = [(0, max_moves)]

    while queue:
        current_node, remaining_moves = queue.pop(0)

        for start_node, end_node, number_of_new_nodes in edges:
            if start_node == current_node:
                # Check if we have enough moves to traverse the edge.
                if remaining_moves >= number_of_new_nodes + 1:

                    new_remaining_moves = remaining_moves - (number_of_new_nodes + 1)
                    for i in range(1, number_of_new_nodes + 1):
                        intermediate_node = (start_node, end_node, i)
                        reachable_nodes.add(intermediate_node)

                    if end_node not in reachable_nodes:
                        reachable_nodes.add(end_node)
                        # Only add to the queue if the end node hasn't
                        # been reached with more moves remaining.
                        queue.append((end_node, new_remaining_moves))

            elif end_node == current_node:
                # Check if we have enough moves to traverse the edge.
                if remaining_moves >= number_of_new_nodes + 1:

                    new_remaining_moves = remaining_moves - (number_of_new_nodes + 1)
                    for i in range(1, number_of_new_nodes + 1):
                        intermediate_node = (start_node, end_node, i)
                        reachable_nodes.add(intermediate_node)

                    if start_node not in reachable_nodes:
                        reachable_nodes.add(start_node)
                        # Only add to the queue if the start node hasn't
                        # been reached with more moves remaining.
                        queue.append((start_node, new_remaining_moves))

    # Sum of normal nodes that can be reached.
    normal_node_count = sum(1 for node in reachable_nodes if isinstance(node, int))
    # Sum of subdivided nodes that can be reached.
    subdivided_node_count = sum(1 for node in reachable_nodes if not isinstance(node, int))

    return normal_node_count + subdivided_node_count

import heapq

def reachableNodes(edges, max_moves, number_of_nodes):
    adjacency_list = [[] for _ in range(number_of_nodes)]
    for u, v, weight in edges:
        adjacency_list[u].append((v, weight + 1))
        adjacency_list[v].append((u, weight + 1))

    # Priority queue to store nodes to visit next, by distance from start
    priority_queue = [(0, 0)]
    distances = {0: 0}
    reachable_nodes = 0

    while priority_queue:
        distance, current_node = heapq.heappop(priority_queue)

        if distance > distances.get(current_node, float('inf')):
            continue

        reachable_nodes += 1

        # Explore neighbors of the current node
        for neighbor, edge_weight in adjacency_list[current_node]:
            new_distance = distance + edge_weight

            if new_distance <= max_moves:
                if new_distance < distances.get(neighbor, float('inf')):
                    distances[neighbor] = new_distance
                    heapq.heappush(priority_queue, (new_distance, neighbor))

    subdivided_nodes_reached = 0
    for u, v, edge_weight in edges:
        # Calculate how many nodes in the edge (u, v) can be reached
        distance_u = distances.get(u, float('inf'))
        distance_v = distances.get(v, float('inf'))

        reachable_from_u = max(0, max_moves - distance_u)
        reachable_from_v = max(0, max_moves - distance_v)

        # Avoid double-counting nodes
        subdivided_nodes_reached += min(edge_weight, reachable_from_u + reachable_from_v)

    # We want to count all nodes reachable given maxMoves.
    return reachable_nodes + subdivided_nodes_reached