Description

You are given a forest with $n$ nodes, with no edges at the beginning.

There are $m$ operations, of two types:

$1\ u_1\ v_1\ u_2\ v_2\ w$: Build a directed portal. From all nodes on the simple path $u_1 \rightarrow v_1$, you can pay cost $w$ to reach all nodes on the simple path $u_2 \rightarrow v_2$. If $u_1$ and $v_1$ are not connected, or $u_2$ and $v_2$ are not connected (connectivity is determined only by edges added by type $2$ operations), then ignore this operation.

$2\ u\ v\ w$: Add an undirected edge of cost $w$ between nodes $u$ and $v$. If $u$ and $v$ are already connected (connectivity is determined only by edges added by type $2$ operations), then ignore this operation.

After these $m$ operations, find the minimum cost from node $s$ to every node.

Input Format

The first line contains three positive integers $n, m, s$, representing the number of nodes in the tree, the number of operations, and the starting node.

The next $m$ lines each contain several positive integers, describing one operation.

Output Format

Output one line with $n$ integers. The $i$-th integer is the minimum cost from node $s$ to node $i$. In particular, if node $i$ cannot be reached, output -1.

9 11 5
2 2 1 2
2 3 1 5
2 4 2 10
2 5 3 9
2 6 5 3
2 7 6 6
2 8 7 2
2 9 4 2
1 1 1 4 9 2
1 8 5 1 6 1
1 3 6 9 6 1

1 1 1 1 0 1 7 9 1

Hint

[Sample Explanation]

This is the tree given in the sample (strictly speaking, this tree is also a chain):

There are three portals, and two of them are like this:

• From node $1$, you can pay cost $2$ to reach all nodes on the simple path $4 \rightarrow 9$ (that is, nodes $4$ and $9$).
• From all nodes on the simple path $8 \rightarrow 5$ (that is, nodes $8, 7, 6, 5$), you can pay cost $1$ to reach all nodes on the simple path $1 \rightarrow 6$ (that is, nodes $1, 3, 5, 6$).

It is easy to see that starting from node $5$, the minimum costs to reach the other nodes are: $1, 1, 1, 1, 0, 1, 7, 9, 1$.

[Constraints]

For test points $1, 2$, $1 \le n \le 100$, $1 \le m \le 300$.

For test points $3, 4$, $1 \le n \le 1000$, $1 \le m \le 3000$.

For $100\%$ of the data, $1 \le n \le 50000$, $1 \le m \le 10^6$, $1 \le u,v \le n$, $1 \le w \le 100$.

For test points $1$ to $10$, each is worth $5$ points.

For test points $11, 12$, each is worth $25$ points.

Translated by ChatGPT 5