def second_minimum_time_brute_force(number_of_nodes, edges, time_to_travel, change):
    # Generate all possible paths from node 1 to node n.
    all_paths = find_all_paths(number_of_nodes, edges, 1, number_of_nodes)

    path_times = []
    for path in all_paths:
        current_time = 0
        for i in range(len(path) - 1):
            current_time += time_to_travel
            # Simulate traffic lights: wait if needed.
            light_phase = (current_time // change) % 2
            if light_phase == 1:
                current_time += change - (current_time % change)
        path_times.append(current_time)

    # Sort all travel times to find the minimum and second minimum.
    path_times.sort()

    minimum_time = path_times[0]

    # Find the second minimum time, ensuring it's different from the minimum.
    for time in path_times:
        if time > minimum_time:
            return time

    return -1

def find_all_paths(number_of_nodes, edges, start_node, destination_node):
    graph = {i: [] for i in range(1, number_of_nodes + 1)}
    for source, destination in edges:
        graph[source].append(destination)
        graph[destination].append(source)

    paths = []
    
    def dfs(current_node, current_path):
        current_path.append(current_node)
        if current_node == destination_node:
            paths.append(current_path.copy())
        else:
            for neighbor in graph[current_node]:
                if len(current_path) < 2 * number_of_nodes: #avoid cycles
                    dfs(neighbor, current_path)
        current_path.pop()

    dfs(start_node, [])
    return paths

from collections import deque

def second_minimum_time_to_reach_destination(number_of_nodes, edges, time, change):

    graph = [[] for _ in range(number_of_nodes + 1)]
    for source, destination in edges:
        graph[source].append(destination)
        graph[destination].append(source)

    shortest_times = [[float('inf')] * 2 for _ in range(number_of_nodes + 1)]
    shortest_times[1][0] = 0

    queue = deque([(1, 0)])

    while queue:
        current_node, current_time = queue.popleft()

        for neighbor in graph[current_node]:
            travel_time = current_time + time

            #Need to wait for green light if red.
            wait_time = (travel_time // change) % 2
            if wait_time == 1:
                travel_time += change - (travel_time % change)

            if travel_time < shortest_times[neighbor][0]:
                shortest_times[neighbor][1] = shortest_times[neighbor][0]
                shortest_times[neighbor][0] = travel_time
                queue.append((neighbor, travel_time))
            elif shortest_times[neighbor][0] < travel_time < shortest_times[neighbor][1]:

                #If it's faster than second best, update.
                shortest_times[neighbor][1] = travel_time
                queue.append((neighbor, travel_time))

    return shortest_times[number_of_nodes][1]