Taco Path Problem

You are given a directed graph with n nodes and m edges. Each edge is represented by a triplet \( (u, v, t) \) which means there is a directed edge from node u to node v with travel time t. Your task is to compute the shortest travel times from a given starting node to all other nodes, with the twist that each node is allowed to be processed at most two times.

If a node is unreachable from the starting node, output -1 for that node. The additional constraint forces you to modify the classic Dijkstra's algorithm by limiting the number of times a node can be relaxed. Efficient use of a priority queue is required to pass all test cases.

inputFormat

The input is read from stdin and has the following format:

1. The first line contains two integers \(n\) and \(m\) which are the number of nodes and the number of edges respectively.
2. The next \(m\) lines each contain three integers \(u\), \(v\), and \(t\) representing a directed edge from node \(u\) to node \(v\) with a travel time of \(t\).
3. The last line contains one integer representing the starting node.

outputFormat

Output a single line to stdout containing n space-separated integers. The i-th integer is the shortest travel time from the starting node to node \(i\). If a node is not reachable, output -1 for that node.

5 6
1 2 5
1 3 10
2 4 3
3 4 2
4 5 1
3 1 7
1

0 5 10 8 9