Minimum Travel Cost

In this problem, you are given a graph representing a network of cities and bidirectional roads. There are ( n ) cities and ( m ) roads. Each city ( i ) has a safety level ( s_i ). Every road connecting two cities is specified by three integers ( u ), ( v ), and ( t ), where ( t ) indicates the type of the road. You can travel along a road if either ( t = 0 ) or the safety level of the destination city is not lower than that of the current city (i.e. ( s_v \ge s_u )). The cost to traverse a road is ( 1 ) if ( t = 0 ) and ( 2 ) if ( t = 1 ). Your task is to determine the minimum travel cost required to go from city 1 to city ( n ). If it is impossible to reach city ( n ), output ( -1 ).


Note: When ( n=1 ) (only one city), the answer is ( 0 ).

inputFormat

The input is read from stdin and has the following format:

• The first line contains two integers ( n ) and ( m ) separated by a space, where ( n ) is the number of cities and ( m ) is the number of roads.
  
• The second line contains ( n ) integers ( s_1, s_2, \ldots, s_n ), representing the safety levels of the cities.
  
• The following ( m ) lines each contain three integers ( u ), ( v ), and ( t ), representing a road between cities ( u ) and ( v ) with type ( t ).

outputFormat

Output a single integer to stdout representing the minimum travel cost from city 1 to city ( n ). If it is impossible to reach city ( n ), output ( -1 ).## sample

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

4