Round Trip Planning with Limited Dangerous Bridges

A country consists of \(N\) islands numbered from \(0\) to \(N-1\), connected by several bidirectional bridges. For each bridge one can only allow one person at a time. Some of these bridges are in poor condition (called dangerous bridges) and each dangerous bridge can be used at most twice in the entire process. The remaining bridges (safe bridges) may be used arbitrarily many times.

Alice wants to travel between islands \(a_1\) and \(a_2\) for \(a_n\) round trips (one round trip counts as going from \(a_1\) to \(a_2\) and back from \(a_2\) to \(a_1\)). Bob wants to do \(b_n\) round trips between islands \(b_1\) and \(b_2\). During all these trips, no dangerous bridge may be crossed more than twice in total. Determine whether it is possible for both Alice and Bob to complete their desired round trips.

In other words, if a trip uses a dangerous bridge then for that trip the dangerous bridge is used twice (once in each direction), and hence such a bridge can only be allocated to at most one round trip. However, if there is a safe route (a path using only safe bridges) between the endpoints then the trips may be repeated arbitrarily. Note that if both persons have to use dangerous bridges then they share the limited capacities on dangerous bridges; they cannot both use the same dangerous bridge beyond its allowed two crossings.

The paths for each trip may be chosen arbitrarily (and may be different for different trips) as long as the dangerous bridge usage over all trips does not exceed the limit on any dangerous bridge.

Note: All formulas are written in \(\LaTeX\) format.

inputFormat

The input is given from standard input in the following format:

N M
u1 v1 t1
u2 v2 t2
... 
 uM vM tM
a1 a2 a_n
b1 b2 b_n

Here, \(N\) is the number of islands and \(M\) is the number of bridges. Each of the next \(M\) lines describes a bridge connecting islands \(u\) and \(v\) with a type indicator \(t\) (\(t = 0\) means a safe bridge; \(t = 1\) means a dangerous bridge). Islands are numbered from \(0\) to \(N-1\). The next line contains three integers: \(a_1\), \(a_2\), and \(a_n\) (the two islands between which Alice needs to make \(a_n\) round trips). The last line contains three integers: \(b_1\), \(b_2\), and \(b_n\) (the two islands between which Bob needs to make \(b_n\) round trips).

outputFormat

Output a single line to standard output: YES if both Alice and Bob can complete their trips without exceeding the dangerous bridges' limits; otherwise, output NO.

sample

4 4
0 1 0
1 2 1
2 3 0
3 0 1
0 2 1
1 3 1

YES