The Gravity Well Navigator | Coding Challenges

Description

Hard

The Gravity Well Navigator

A spacecraft navigates through a star system with n planets. Travel between planets is affected by gravity wells.

The system is represented as a weighted directed graph. Edge weight from planet i to planet j represents the base travel time. However, planet i has a gravity factor g[i] that multiplies the travel time of all outgoing edges.

Find the minimum time to travel from planet 1 to planet n. If impossible, return -1.

Actual travel time from i to j = base_time[i][j] * g[i]

Input Format

The first line contains two integers n and m (planets and routes). The second line contains n space-separated integers representing gravity factors g[i]. The next m lines each contain three integers: from, to, and base_time.

Output Format

Print the minimum travel time, or -1 if impossible.

Examples

Example 1

Input

3 3 1 2 1 1 2 5 2 3 3 1 3 10

Output

ExplanationPath 1->3 direct: base_time=10, gravity=1, actual=10. Path 1->2->3: 5*1 + 3*2 = 5+6=11. Best is 10.

Example 2

Input

2 1 2 3 1 2 5

Output

ExplanationOnly path is 1->2 with base_time=5 and gravity=2, so actual=10.

Constraints

•

2 ≤ n ≤ 1000

•

1 ≤ m ≤ 10000

•

1 ≤ g[i] ≤ 100

•

1 ≤ base_time ≤ 1000

Code

Error

Case 1

Case 2

Input

3 3 1 2 1 1 2 5 2 3 3 1 3 10

Output

No output

Expected