题目描述

【如果不想看题面请阅读分割线以下部分】

$$\text{Onde\space a\space terra\space acaba\space e\space o\space mar\space começa} $$

15 世纪末，是一个伟大时代的开始。自此之后，人们开始逐渐认识到大千世界的险恶与奇丽，开始前仆后继地展开一个又一个不可思议的冒险，开始缓缓地驾驭那波涛汹涌、变幻莫测的大海。

15 世纪末，是一个伟大时代的开始。为了征服海洋，人们集人类之智慧，制造出方舟巨轮；汇天地之灵怪，制造出罗盘、六分仪。海上的康庄大道从此建立，人们航行于各地，商贸随之诞生。

15 世纪末，是一个伟大时代的开始。商品与金钱象征着欲望，在海上流动了起来。原先分隔的黄金汇聚成大金库，让人们尝到了商业的甜头。贸易的花朵开遍整个欧洲，航线上船只往来不绝，财富源源不断地从海上涌出。

更多

……

大航海时代，是人类文明崭新的起点。

海上经商，商人们必须对航路有充分的了解。欧洲的城市不计其数，航路更是数不胜数。当然，人们无需知晓所有城市的位置，更无需清楚所有航路的情况。人们只需要知道，有几个主要城市，并且有几条海上航路连接着它们即可，其他的城市与航路都是次要的，不会带来过多收益。

商船沿着航路往来于城市之间。它们每到一个城市，卸下一些货品，城市里的商人便会根据货品的数目给出相应的报酬。这些报酬由船主收取，并将部分报酬分发给水手们。不过大家并不关心这件事，他们只会关心一艘船获得的总收益。

商船的航行总会伴随着危险与损失。海上的天气难以预测，船只随时都可能会被大浪吞没，或者被飓风刮得千疮百孔。不过这些情况比较特殊，我们并不考虑。我们考虑的是，商船在航行过程中的必要支出。一趟航行往往需要几星期甚至几个月的时间。在这段时间里，船员需要淡水与食物，船也需要适当的维护。人们总结经验发现，一段航行的必要支出与航行距离和载货量有直接关系。

大航海时代的人们就是在这些规律下生活的，考量着商船的支出与收益，缓行于茫茫大海之上，每日如此，单调而无趣。大航海时代，对于大部分人来说，或许并没有那么伟大。

当然，生于现代的我们不必在意这些东西。这也是当然的，现代人怎么会为古代人考虑什么东西呢？

然而，小 L 和小 K 发现他们必须开始考虑这些事物了，因为他们不小心掉进了虫洞，回到了大航海时代。回到过去的他们用唯一的财产：手机，换来了一艘船和一船货物。为了生存，他们要驾驶着这艘船航行于海上，用货物与商人们换取钱财。

---

小 L 和小 K 通过调查了解了海上贸易的一些基本规律。共有 $n$ 个主要城市和 $m$ 条连接着它们的航道，船只能沿着这些航道航行。注意航道是单向的，因为如果是双向，航线就容易交叉，发生事故。第 $i$ 条航道的距离为 $dis_i$，若商船在经过此航道时载货量（下称货物量）为 $p$，则航行完此航道需花费 $p\times dis_i$ 的金币。商船到达一个城市，会卸下部分货物与商人交易。每座城市都有一个大商人，会根据 船上卸下 的货物量付给商船一定的金币。每座城市的大商人不同，标准也不一样。第 $i$ 座城市的大商人标准为 $mea_i$，若商船在 $i$ 号城市卸下量为 $p$ 的商品，大商人会付给商船 $p\times mea_i$ 的金币。商船每到达一座城市，只会与大商人进行一次交易。当然，一座城市可以重复到达，每次到达都会与大商人进行交易。

小 L 和小 K 需要遵循这些规律，沿着航道进行海上贸易。小 L 和小 K 在一开始总共有量为 $q$ 的货品。小 L 和小 K 本该精打细算，详细计算出他们在每座城市应该卸下的货物量。但是小 L 和小 K 是懒癌晚期患者，并不想这样做。他们随便想了两个正整数 $s,t$，于是如果需要卸下货物，他们便会卸下总货物量 $\frac{s}{s+t}$ 的货物。

在他们的商贸之旅开始之前，小 L 和小 K 就已经研究出了回到现代的方法。但是他们并不着急回去。因为回溯时间导致的时空错位，小 L 和小 K 身上的时间是静止的。也就是说他们拥有无限的时间。他们决定利用此原理在这个时代大赚一笔。小 L 和小 K 可以选择从任意一座城市出发。他们希望知道从每座城市出发，可以赚到的最大金币数量是多少。当然因为他们比较懒，这个问题由你来解决。

需要注意的是，尽管在大航海时代分数的运算并没有普及，但小 L 和小 K 为了自己方便而将他们得到的信息部分用分数（有理数）来表示。也就是说，虽然 $dis_i,mea_i,q$ 是由当时的人们给出的，所以是整数，但是货物量和金币量可以是分数，即小 L 和小 K 用有理数的计算法则计算自己的收益。小 L 和小 K 在出发的城市也会进行交易。

输入格式

第一行，五个正整数 $n,m,s,t,q$。

第二行， $n$ 个正整数，第 $i$ 个数表示 $mea_i$。

接下来 $m$ 行，每行三个正整数 $a,b,dis_i$，表示从城市 $a$ 到城市 $b$ 有一条长为 $dis_i$ 的单向航道。

输出格式

共 $n$ 行，第 $i$ 行表示从 $i$ 号城市出发可以赚到的最大金币数量，输出格式见下文。

关于分数的输出格式：

可能以 a/b 的形式输出，表示分数 $\frac{a}{b}$，其中 $a,b$ 为正整数。也可能以 -a/b 的形式输出，表示分数 $-\frac{a}{b}$，其中 $a,b$ 为正整数。也可能以 a 的形式输出，表示整数 $a$。注意 $\gcd(a,b)$ 一定为 $1$。如果 $b$ 为 $1$，则必须以 a 的形式输出。

3 3 1 1 2
100 200 300
1 1 50
1 2 2
2 3 1

545/2
349
300

提示

【样例说明】

$\frac{s}{s+t}=\frac{1}{2}$，小 L 和小 K 每次会卸下一半的货物进行交易。

从 $1$ 号城市出发：先在 $1$ 号城市进行交易，用 $2\times\frac{1}{2}=1$ 的货物量交易，获得金币 $1\times 100=100$，剩余货物量 $2-1=1$。之后如果走 $1\rightarrow1$ 的航道，会再花费 $1\times 50=50$ 的金币回到城市 $1$，很不划算。如果走 $1\rightarrow2$ 的航道，只需要再花费 $1\times 2=2$ 的金币就可以到达城市 $2$。到达城市 $2$ 进行交易，用 $1\times\frac{1}{2}=\frac{1}{2}$ 的货物量交易，获得金币 $\frac{1}{2}\times 200=100$，剩余货物量 $1-\frac{1}{2}=\frac{1}{2}$。接下来走 $2\rightarrow3$，花费 $\frac{1}{2}\times1=\frac{1}{2}$ 的金币。到达城市 $3$，用 $\frac{1}{2}\times\frac{1}{2}=\frac{1}{4}$的货物量交易，交易获得金币 $\frac{1}{4}\times300=75$，剩余货物量 $\frac{1}{2}-\frac{1}{4}=\frac{1}{4}$。总获利 $100-2+100-\frac{1}{2}+75=\frac{545}{2}$。

从 $2$ 号城市出发：走 $2\rightarrow3$，在 $2,3$ 号城市交易，获利 $200-1+150=349$。

从 $3$ 号城市出发：在 $3$ 号城市交易，获利 $300$。

【数据范围】

对于 $10\%$ 的数据，$n\le 3,m\le 9$，$s,t,q,mea_i,dis_i\le10$。

对于 $50\%$ 的数据，$n\le 10,m\le 100$，$s,t,q,mea_i,dis_i\le10$。

对于另外 $10\%$ 数据，$m=n$，且对于任意正整数 $i\in[1,n]$，编号为 $i$ 的城市有一条到编号为 $(i\mod n)+1$ 的城市的航道。

对于另外 $10\%$ 数据，对于任意正整数 $i\in[1,n]$，若存在航道 $i\rightarrow j$，则 $j>i$。

对于 $100\%$ 的数据，$n\le 50,m\le 500$，$s,t,q,mea_i,dis_i\le10^4$。

【补充说明】

城市从 $1$ 到 $n$ 编号。

请注意本题特殊的时空限制。

为了防止题目过于卡常，本题 提供 八聚氧 ，直接加在代码最前提交即可。保证标程在加上八聚氧后通过每个数据点的最大用时小于时限的一半。请大胆尝试解法。