- 44

## Statement

## Goal

A driver is on a road network with`n`junctions and

`m`roads with two specific positions

`s`and

`t`.

Each junction of the network can be associated with a time window

`[b,e]`: the driver can go through that intersection only between times

`b`and

`e`. Every other junction is free : the driver can cross it at any time. Each road is associated with a duration: the time a car needs to drive through that road.

**The roads are directed : the car cannot go through a road backward.**

Your goal is to decide if a driver can go from

`s`to

`t`such that, for each junction associated with a time window

`[b,e]`, the moment

`r`when the driver reaches that junction belongs to its window : b <= r <= e. If the junction has no time window, the driver can reach it at any time.

The driver starts in

`s`at time

**The driver cannot wait. Once he reaches a junction, he must go though an outgoing road of that junction.**

The time windows are always closed intervals.

Here is an example where <, >, ^ and v represent roads (and the directions).

s > u > w > t

v ^ v ^

x > y > z > r

The time window on x, u and y is

The time window on w, z and r is

The time window on t is

The duration on each arc is

It is possible to go from s to t with that path.

s t

v ^

x > y > z > r

The driver would be in x at time 1, y at time 2, z at time 3, r at time 4 and t at time 5. Each time fits within the specified time window.

In this example with the same time windows and same durations :

s > u > w > t

v ^ v ^

x > y z > r

You cannot go from s to t, because you must go through w in order to reach t and it is not possible to be in w between time 3 and 5 and in u between time 1 and 2:

- either the driver goes from s to u and arrives at w at time 2;

- or it uses the path s x y u w and arrives at u at time 3.

Input

**Line 1 :**Three integers

`n`,

`m`and

`ntw`the number of junctions and roads in the network and the number of junctions with a time window. The junctions are numbered from 0 to

`n-1`.

**Line 2 :**Two integers

`s`and

`t`, the origin and the destination of the driver

**three integers**

`ntw`next lines :`v`,

`b`and

`e`, a junction v, the beginning and the end of the time window of that junction.

**three integers**

`m`next lines :`u`,

`v`and

`d`, the origin, the destination and the duration of each arc.

Output

**Line 1 :**print

`s`to

`t`satisfying the time windows constraints. Otherwise, print

Constraints

1 <=

1 <=

0 <=

0 <=

0 <=

`n`<= 101 <=

`m`<= 200 <=

`e`-`b`< 100 <=

`e`,`b`<= 500 <=

`d`<= 25Example

Input

8 10 8 0 3 0 0 0 1 1 2 2 3 5 3 1 7 4 1 2 5 1 2 6 3 5 7 3 5 0 1 1 0 4 1 1 2 1 2 3 1 2 6 1 4 5 1 5 1 1 5 6 1 6 7 1 7 3 1

Output

true

A higher resolution is required to access the IDE

Online Participants

### Channels

### Direct Messages

No private conversations