C1562 【XR-1】逛森林

NaCly_Fish 和 PinkRabbit 是好朋友。

有一天她去森林里游玩，回去跟 PinkRabbit 说：“我发现好多棵会动的树耶！”

PinkRabbit 动了动一只兔耳朵：“这有什么好稀奇的，我用一只兔耳朵就能维护每棵树的形态。”

NaCly_Fish 不服：“不止这样，我还看到有一些传送门，能从一条树枝跳到另一条树枝上呢！”

PinkRabbit 动了动另一只兔耳朵：“这有什么好稀奇的，我用两只兔耳朵就能统计每个传送门的信息。”

于是 NaCly_Fish 很郁闷，她向你求助，请帮帮她吧。

给你 $n$ 个节点的森林，初始没有边。

有 $m$ 个操作，分为两种：

$1\ u_1\ v_1\ u_2\ v_2\ w$：表示构建一个单向传送门，从 $u_1 \rightarrow v_1$ 简单路径上的所有节点，可以花费 $w$ 的代价，到达 $u_2 \rightarrow v_2$ 简单路径上的所有节点。若 $u_1$ 到 $v_1$ 或 $u_2$ 到 $v_2$ 不连通（由 $2$ 操作产生的边不连通），则忽略此次操作。

$2\ u\ v\ w$：表示将 $u$ 和 $v$ 节点间连一条花费为 $w$ 的无向边，若 $u$ 和 $v$ 之间已连通（由 $2$ 操作产生的边连通）则忽略此次操作。

经过这 $m$ 次操作后，请你求出从 $s$ 节点出发，到每个节点的最小花费。

样例输入 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 1 0 1 7 9 1