该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题面描述

有 N 个小岛，编号为 1 ~ N。

小岛之间的货物运输可能通过轮船航运，也可能通过海底隧道。

有 M 条轮船航线，编号为 1 ~ M。轮船航线是双向通行的。

有 K 条海底隧道，编号为 1 ~ K。海底隧道是单向通行的。

每条航线或隧道都有一个通行时间。航线的通行时间都是非负整数。隧道则不一定，有些隧道的通行时间为负数，表示经过这些隧道可以穿越回过去。

另外，为了保证安全，岛屿之间的路线已经做了特别规划。如果从 u 到 v 有一条隧道，那就不可能再有任何路线可以从 v 回到 u。（输入数据保证这一点）

每天，小 A 都要从小岛 S 出发，向某一个小岛上运输货物。他想知道，对于小岛 i，他从 S 出发到达小岛 i 所需的时间最少是多少？

输入格式

第 $1$ 行：四个整数 $N, M, K, S$

接下来 $M$ 行：每行三个整数 $u, v, w$，描述一条航线连接的两个小岛的编号和通行时间。

接下来 $K$ 行：每行三个整数 $x, y, z$，描述一条隧道的起点、终点编号和通行时间。

输出格式

共 $N$ 行，第 $i$ 行输出小 A 从小岛 $S$ 出发到达小岛 $i$ 所需的最少时间（答案可能为负）。如果不可能到达某个小岛，则在对应行输出 Impossible

样例输入

6 3 3 4 
1 2 5 
3 4 5 
5 6 10 
3 5 -100 
4 6 -100 
1 3 -10

样例输出

Impossible
Impossible 
5 
0 
-95 
-100

数据范围

$1 ≤ N ≤ 25,000，1 ≤ M, K ≤ 50,000，1 ≤ u, v, x, y, S ≤ N，0 ≤ w ≤ 10,000，|z| ≤ 10,000$