Background

NaCly_Fish and PinkRabbit are good friends.

One day, she went to the forest for fun. After coming back, she said to PinkRabbit: “I found many trees that can move!”

PinkRabbit twitched one rabbit ear: “What is so strange about that? With one rabbit ear, I can maintain the shape of every tree.”

NaCly_Fish was not convinced: “Not only that. I also saw some portals. They can jump from one branch to another!”

PinkRabbit twitched the other rabbit ear: “What is so strange about that? With two rabbit ears, I can count the information of every portal.”

So NaCly_Fish felt very depressed, and she asked you for help. Please help her.

What? You are not willing to help?

Then she will not give you the points for this problem.

Problem 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