You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

In this lab, you are a network engineer managing a large computer network. Your system connects several servers (nodes). When a new network connection is established (an edge), it has a specific latency, measured in milliseconds (ms). This is the time it takes for a data packet to travel from one server to the other.

Because this latency represents time, it is always a positive cost (you can't travel back in time!).

Your goal is to implement a routing calculator. Given a "source" server (the node you are at), you need to find the best route to all other servers in the network.

For every possible destination, you must compute two things:

1. The total latency of the fastest possible path (the shortest path cost).
2. The "next stop" (or "next hop"). This is the first server on that fastest path that you should send your packet to.

For example, if the best path from $S$ to $D$ is $S \to A \to B \to D$, the total latency is the sum of latencies $(S, A) + (A, B) + (B, D)$, and the next stop is $A$.

You will be given the number of servers, a list of all the network links, and a single source server.

You will need to:

1. Represent the Network: Use an adjacency list to store the graph. All connections are bi-directional.
2. Implement Dijkstra's Algorithm:
   • Use a priority queue (min-heap) to efficiently select the next node to visit.
   • Hint: To find the "next stop," you will need to store the predecessor (or parent) of each node in the shortest path tree. After Dijkstra's is complete, to find the next hop for a destination $T$, you must trace the path $S \to \dots \to \text{parent}[T] \to T$ all the way back to $S$. The "next hop" is the node on this path that comes immediately after $S$.

Format

Input

• The first line contains two integers, $V$ and $E$ ($1 \leq V \leq 1000$, $0 \leq E \leq 5000$), representing the number of servers (nodes) and the number of network connections (edges). The servers are numbered $0$ to $V-1$.
• The next $E$ lines each contain three integers: $U$, $V$, and $W$ ($0 \leq U, V < V$, $1 \leq W \leq 1000$). This represents a bi-directional connection between server $U$ and $V$ with a latency of $W$ ms.
• The last line contains a single integer $S$ ($0 \leq S < V$), representing the source server.

Output

• Print $V$ lines of output, one for each server $i$ (from $i=0$ to $i=V-1$).
• Each line must contain two space-separated integers:
  1. The minimum latency from the source $S$ to server $i$.
  2. The ID of the next hop on the path from $S$ to $i$.
• If server $i$ is the source itself ($i == S$), output 0 -1 (latency is 0, and there is no next hop).
• If server $i$ is unreachable from $S$, output -1 -1.

Samples

5 7
0 1 10
0 2 3
1 2 1
1 3 2
2 3 8
2 4 2
3 4 5
0

0 -1
4 2
3 2
6 2
5 2

Explanation for Sample 1: The source is Node 0.

• To 0 (Source): Latency is 0, next hop is -1. Output: 0 -1
• To 1: Path is $0 \to 2 \to 1$. Latency = 3 + 1 = 4. The next hop from 0 is 2. Output: 4 2
• To 2: Path is $0 \to 2$. Latency = 3. The next hop from 0 is 2. Output: 3 2
• To 3: Path is $0 \to 2 \to 1 \to 3$. Latency = 3 + 1 + 2 = 6. The next hop from 0 is 2. Output: 6 2
• To 4: Path is $0 \to 2 \to 4$. Latency = 3 + 2 = 5. The next hop from 0 is 2. Output: 5 2

---

4 2
0 1 5
1 2 2
0

0 -1
5 1
7 1
-1 -1

Explanation for Sample 2: The source is Node 0.

• To 0 (Source): Latency is 0, next hop is -1. Output: 0 -1
• To 1: Path is $0 \to 1$. Latency = 5. The next hop from 0 is 1. Output: 5 1
• To 2: Path is $0 \to 1 \to 2$. Latency = 5 + 2 = 7. The next hop from 0 is 1. Output: 7 1
• To 3: Node 3 is unreachable. Output: -1 -1

Hint

• Since all link latencies (edge weights) are positive, this is a classic application of Dijkstra's algorithm.
• To retrieve the "next hop," you will need to backtrack from each destination node to the source using the parent array built during Dijkstra's execution.

Limitation

1s, 128MiB for each test case.