Maximizing Trade Profit in Country C

Country C has n major cities and m roads. Each road connects two distinct cities, and no pair of cities is connected by more than one road. Some roads are one‐way and some are two‐way (each two–way road is counted as one road).

Every city has a fixed price for a special commodity, the crystal ball. The buying and selling price in a city are the same. When merchant Arlong tours Country C, he starts from city 1 and must finish at city n. He may pass through cities multiple times and his route does not need to cover all cities.

Arlong plans to earn travel funds by trading his favorite commodity. During his journey, he is allowed to perform at most one buy–sell trade: he buys the crystal ball in one city and, at some later visited city (on his route), sells it. His profit is computed as the difference between the selling price and the buying price. If no positive profit is possible, he chooses not to trade.

Formally, let the price in city i be \(p_i\). Arlong chooses two cities \(i\) and \(j\) (where the visit to \(i\) precedes that to \(j\) along some route from city 1 to city \(n\)), and his profit is \(p_j - p_i\). He wants to maximize his profit over all such feasible routes.

Example: Suppose Country C has 5 cities with crystal ball prices 4, 3, 5, 6, and 1, respectively, and the road connections are as follows:

• Road from 1 to 2 (one–way)
• Road from 2 to 3 (one–way)
• Road from 3 to 5 (one–way)
• Road from 1 to 4 (one–way)
• Road between 4 and 5 (two–way)

Then one feasible route is 1 → 2 → 3 → 5 with a trade of buying at city 2 (price 3) and selling at city 3 (price 5) for a profit of 2. Another route is 1 → 4 → 5 → 4 → 5 with a trade of buying at the first visit to city 5 (price 1) and selling at the later visit to city 4 (price 6) for a profit of 5. The maximum profit obtainable is 5.

inputFormat

The first line of input contains two integers n and m, where n is the number of cities and m is the number of roads.

The second line contains n integers: p1 p2 ... pn, where pi is the price of the crystal ball in city i.

Then follow m lines. Each line contains three integers: u v t, indicating there is a road between cities u and v. If t = 1, the road is one–way from u to v; if t = 2, the road is two–way (i.e. both u → v and v → u exist).

outputFormat

Output a single integer representing the maximum profit Arlong can earn. If no positive profit trade is possible, output 0.

sample

5 5
4 3 5 6 1
1 2 1
2 3 1
3 5 1
1 4 1
4 5 2

5