F. Volcanic Islands
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Volcanoes are erupting over the ovine homeland! Help the Sheep King escape the lava.

There are $$$n$$$ islands connected by $$$m$$$ undirected bridges. Each bridge has a length $$$w$$$: crossing that bridge takes exactly $$$w$$$ days (for both the sheep and the lava).

Each island $$$i$$$ has a volcano that erupts on day $$$a_i$$$. When a volcano erupts, all bridges connected to that island burn down and become unusable.

Lava spreads through the bridge network over time, using the same travel times as the Sheep King (it needs $$$w$$$ days to cross a bridge of length $$$w$$$). If lava reaches an island before its volcano erupts, that island burns at the moment lava arrives.

The Sheep King starts on island $$$1$$$ at day $$$0$$$ and wants to reach island $$$n$$$ to escape. If he arrives at an island exactly when it burns, he is considered safe and may still depart from it at that time.

Input

The first line contains an integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of test cases.

For each test case:

  • The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \le n \le 10^5,\ 0 \le m \le 10^5)$$$.
  • The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — the eruption days of the volcanoes.
  • Each of the next $$$m$$$ lines contains three integers $$$x_j$$$, $$$y_j$$$, and $$$w_j$$$ $$$(1 \le x_j \lt y_j \le n, 1 \le w_j \le 10^9)$$$ denoting an undirected bridge between islands $$$x_j$$$ and $$$y_j$$$ of length $$$w_j$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, print Yes (case-insensitive) if it is possible to travel from island $$$1$$$ to island $$$n$$$. Otherwise, print No (case-insensitive).

Examples
Input
1
3 2
100 2 100
1 2 2
2 3 2
Output
YES
Input
2
5 7
46 34 5 60 36
1 3 23
1 3 29
1 5 7
2 5 25
4 5 8
4 5 11
4 5 29
5 7
25 53 5 49 7
1 2 4
1 4 7
1 5 23
2 5 23
2 5 24
3 4 12
4 5 20
Output
YES
NO
Note

The Sheep King can travel from island $$$1$$$ to island $$$2$$$ in $$$2$$$ days. He arrives at island $$$2$$$ on day $$$2$$$, exactly when it burns. He is still safe, so he can continue to island $$$3$$$ and arrive there on day $$$4$$$. The answer is Yes.