Forest Portals and Undirected Paths

You are given a forest with n nodes and initially no edges. There are m operations; each operation is one of two types:

• Type 1: 1 u1 v1 u2 v2 w. This operation attempts to build a one‐directional portal. First, consider the unique simple path between nodes u1 and v1 in the forest formed by the undirected edges added by Type 2 operations. Similarly, consider the unique simple path between u2 and v2 in the forest. If either pair is not connected, ignore this operation. Otherwise, for every node a on the simple path from u1 to v1 and every node b on the simple path from u2 to v2, add a directed edge from a to b with cost w.
• Type 2: 2 u v w. This operation attempts to add an undirected edge between nodes u and v with cost w. If u and v are already connected by undirected edges (i.e. in the forest), ignore this operation.

After processing all m operations, compute the minimum cost from a given starting node s to every other node. If a node is unreachable, its minimum cost is -1.

Note: When constructing the simple paths for portal operations, the path between two nodes u and v (if they are connected) is unique since the undirected edges form a forest. Also, all operations are processed in the order given.

Formulas:

For a portal operation, if both paths exist, add directed edges from every a in Path(u1, v1) to every b in Path(u2, v2) with cost w. In LaTeX, this can be written as: $$ \forall a \in Path(u_1,v_1),\; \forall b \in Path(u_2,v_2): \; cost(a \to b)=w. $$

inputFormat

The first line contains three integers n, m and s (1 ≤ s ≤ n), representing the number of nodes, the number of operations, and the starting node respectively.

The next m lines each describe an operation. An operation is in one of the following formats:

• 1 u1 v1 u2 v2 w — a portal operation.
• 2 u v w — an undirected edge operation.

It is guaranteed that any cost w is a positive integer.

outputFormat

Output n space-separated integers, where the i-th integer represents the minimum cost from node s to node i. If a node is unreachable, output -1 for that node.

sample

5 3 1
2 1 2 3
2 2 3 4
1 1 2 2 3 10

0 3 7 -1 -1