dangerous-dungeon

See Russian Translation

David is playing a video game set in a dungeon. The dungeon has n interesting points and m one way tunnels connecting those points. The i-th tunnel starts at point ai and ends at point bi and takes ci units of time to traverse. Note that it may be possible that there are two tunnels connecting the same pair of points, and even more strangely, a tunnel that goes back to the same point.

David is currently at the point labeled 0, and wishes to travel to the point n-1 using the smallest amount of time.

David discovered that some points become dangerous at some moments of time. More specifically, for each point, David found an integer oi such that point i is dangerous at all times t satisfying t = oi modulo p. The integer p is the same for every single intersection.

David needs to always be in constant motion, and can't wait at a point. Additionally, he will always be safe in a tunnel, but cannot arrive at a point at the moment it becomes dangerous. 

Help David determine the fastest time he can reach his destination.

Input Format:

The first line of input will contain three space separated integers n,m,p.
The next line of input will contain n space separted integers oi.
The next m lines of input will each contain 3 integers ai, bi, ci

Output Format:

If it is impossible for David to reach point n-1, print -1. Otherwise, print the smallest amount of time it will take David to reach n-1.

Constraints:

For all subtasks:
0 ≤ ai, bi ≤ n-1 
0 ≤ ci ≤ 10^9
0 ≤ oi ≤ p-1

25 pts:
2 ≤ n ≤ 50
1 ≤ m ≤ 250
2 ≤ p ≤ 50

30 pts:
2 ≤ n ≤ 100
1 ≤ m ≤ 10000
2 ≤ p ≤ 500

30 pts:
2 ≤ n ≤ 50
1 ≤ m ≤ 2500
2 ≤ p ≤ 10^9

15 pts:
2 ≤ n ≤ 1000
1 ≤ m ≤ 10000
2 ≤ p ≤ 10^9

SAMPLE INPUT
4 5 5
1 0 2 3
0 1 8
0 2 2
1 3 5
2 3 3
1 2 6

SAMPLE OUTPUT
17

Explanation

The shortest path here is 0->1->2->3.
We can't take the tunnel 0->2 immediately, since point 2 will be dangerous at time T=2.
We can't take the tunnel 1->3 after 0->1, since point 3 will be dangerous at time T=13.
Instead, this roundabout path is the only way for David to get to the exit.

Source: hackerearth | Difficulty: MEDIUM
Tags: Graph algorithms

Mathematics


Solutions: