P5822 [L&K R-03] Age of Discovery

[If you do not want to read the full statement, please read the part below the divider.] $$\text{Onde\space a\space terra\space acaba\space e\space o\space mar\space começa}$$ >_At the end of the 15th century, a great era began. From then on, people gradually came to know the dangers and wonders of the world, started one incredible adventure after another, and slowly learned to navigate the rough and unpredictable sea._ >_At the end of the 15th century, a great era began. To conquer the ocean, people gathered human wisdom to build giant ships; and drew on the mysteries of nature to create the compass and the sextant. From then on, smooth sea routes were established. People sailed to various places, and trade was born._ >_At the end of the 15th century, a great era began. Goods and money, symbols of desire, began to flow across the sea. Gold that was once separated gathered into great vaults, letting people taste the sweetness of business. The flowers of trade bloomed all over Europe, ships traveled endlessly along routes, and wealth poured out from the sea._ >_[More](https://www.luogu.org/paste/k9bqwpps)_ >…… >_The Age of Discovery was a brand-new starting point for human civilization._ To do business at sea, merchants must fully understand the routes. There are countless cities in Europe, and even more routes. Of course, people do not need to know the locations of all cities, nor the details of all routes. They only need to know that there are several major cities and several sea routes connecting them. Other cities and routes are secondary and will not bring much profit. Merchant ships travel between cities along routes. Each time a ship arrives at a city, it unloads some goods, and the merchants in the city pay a corresponding reward based on the amount of goods. The ship owner collects this reward and distributes part of it to the sailors. But nobody cares about that; they only care about the total profit a ship earns. Sailing always comes with danger and loss. The weather at sea is hard to predict; ships may be swallowed by huge waves or torn apart by hurricanes. However, these are special cases and we will not consider them. What we consider is the necessary expenses during sailing. A voyage often takes weeks or even months. During this time, the crew needs fresh water and food, and the ship needs maintenance. From experience, people found that the necessary cost of a voyage is directly related to the sailing distance and the amount of cargo. People in the Age of Discovery lived under these rules, weighing a ship’s expenses and income, moving slowly across the vast sea day after day—monotonous and boring. For most people, the Age of Discovery might not have been that great. Of course, we who live in modern times do not need to care about these things. Naturally, why would modern people think about such things for ancient people? However, Little L and Little K found that they had to start caring about them, because they accidentally fell into a wormhole and returned to the Age of Discovery. After returning to the past, they traded their only property—a mobile phone—for a ship and a shipload of goods. To survive, they must sail this ship on the sea and exchange goods with merchants for money. ---------------------------------- Little L and Little K investigated and learned some basic rules of maritime trade. There are $n$ major cities and $m$ sea routes connecting them, and ships can only sail along these routes. Note that routes are directed, because if they were bidirectional, routes would easily cross and accidents would happen. The distance of the $i$-th route is $dis_i$. If the cargo load (hereinafter called the amount of goods) is $p$ when the ship travels along this route, then completing this route costs $p\times dis_i$ gold coins. When the ship arrives at a city, it unloads part of the goods to trade. Each city has a “big merchant”, who pays the ship a certain amount of gold coins based on the amount of goods **unloaded from the ship**. Big merchants differ from city to city, and so do their standards. The standard of the big merchant in city $i$ is $mea_i$. If the ship unloads $p$ goods in city $i$, the big merchant pays $p\times mea_i$ gold coins. Each time the ship arrives at a city, it trades with the big merchant exactly once. Of course, a city may be visited repeatedly, and each visit triggers a trade with the big merchant. Little L and Little K must follow these rules and conduct maritime trade along the routes. Initially, Little L and Little K have a total amount of goods $q$. They should have planned carefully and computed exactly how much to unload in each city. But they are extremely lazy and do not want to do that. They randomly chose two positive integers $s,t$. Therefore, whenever they need to unload goods, they will unload $\frac{s}{s+t}$ of the total goods currently on the ship. Before their trading journey began, Little L and Little K had already figured out how to return to modern times. But they were not in a hurry to go back. Due to time-space misalignment caused by traveling back in time, time is frozen for them. That is, they have unlimited time. They decided to use this principle to make a fortune in this era. They may choose to start from any city. They want to know, for each starting city, what is the maximum number of gold coins they can earn. Since they are lazy, you are asked to solve this problem. Note that although fraction arithmetic was not widely used in the Age of Discovery, Little L and Little K, for their own convenience, expressed part of the information they obtained using fractions (rational numbers). That is, although $dis_i,mea_i,q$ are integers given by people of that time, the amount of goods and the amount of gold coins may be fractions. Little L and Little K compute their profit using the rules of rational arithmetic. Little L and Little K will also trade in the city where they start.

The first line contains five positive integers $n,m,s,t,q$. The second line contains $n$ positive integers; the $i$-th number denotes $mea_i$. The next $m$ lines each contain three positive integers $a,b,dis_i$, indicating that there is a directed sea route of length $dis_i$ from city $a$ to city $b$.

Output $n$ lines. The $i$-th line denotes the maximum number of gold coins that can be earned starting from city $i$. The output format is described below. About the output format for fractions: It may be printed as ```a/b```, representing the fraction $\frac{a}{b}$, where $a,b$ are positive integers. It may also be printed as ```-a/b```, representing the fraction $-\frac{a}{b}$, where $a,b$ are positive integers. It may also be printed as ```a```, representing the **integer** $a$. Note that $\gcd(a,b)$ is guaranteed to be $1$. If $b$ is $1$, then it must be printed in the form ```a```.

[Sample Explanation.] $\frac{s}{s+t}=\frac{1}{2}$, so each time Little L and Little K will unload half of the goods to trade. Starting from city $1$: first trade in city $1$, trade using $2\times\frac{1}{2}=1$ goods, obtain $1\times 100=100$ gold coins, and the remaining goods are $2-1=1$. If they then take the route $1\rightarrow1$, it will cost another $1\times 50=50$ gold coins to return to city $1$, which is not worth it. If they take the route $1\rightarrow2$, it only costs another $1\times 2=2$ gold coins to reach city $2$. Arriving at city $2$ and trading, they trade using $1\times\frac{1}{2}=\frac{1}{2}$ goods and obtain $\frac{1}{2}\times 200=100$ gold coins, leaving $1-\frac{1}{2}=\frac{1}{2}$ goods. Next, take $2\rightarrow3$, costing $\frac{1}{2}\times1=\frac{1}{2}$ gold coins. Arriving at city $3$, trade using $\frac{1}{2}\times\frac{1}{2}=\frac{1}{4}$ goods, obtain $\frac{1}{4}\times300=75$ gold coins, leaving $\frac{1}{2}-\frac{1}{4}=\frac{1}{4}$ goods. Total profit is $100-2+100-\frac{1}{2}+75=\frac{545}{2}$. Starting from city $2$: take $2\rightarrow3$, trade in cities $2$ and $3$, profit is $200-1+150=349$. Starting from city $3$: trade in city $3$, profit is $300$. [Constraints.] For $10\%$ of the testdata, $n\le 3,m\le 9$, and $s,t,q,mea_i,dis_i\le10$. For $50\%$ of the testdata, $n\le 10,m\le 100$, and $s,t,q,mea_i,dis_i\le10$. For another $10\%$ of the testdata, $m=n$, and for any positive integer $i\in[1,n]$, city $i$ has a route to city $(i\mod n)+1$. For another $10\%$ of the testdata, for any positive integer $i\in[1,n]$, if there exists a route $i\rightarrow j$, then $j>i$. For $100\%$ of the testdata, $n\le 50,m\le 500$, and $s,t,q,mea_i,dis_i\le10^4$. [Additional Notes.] Cities are numbered from $1$ to $n$. Please note the special time limit of this problem. To prevent the problem from being too time-tight, this problem **provides [Octaoxygen](https://www.luogu.com.cn/paste/ky1fh8zk)**. You can paste it directly at the very beginning of your code before submitting. It is guaranteed that, after adding Octaoxygen, the maximum running time of the official solution on each test point is less than half of the time limit. Feel free to try your approach. Translated by ChatGPT 5