Minimum Time Problem Statement

In a city with ‘N’ junctions and ‘M’ bi-directional roads, each junction is connected to other junctions with specified travel times. No road connects a junction to itself, and only one road connects any pair of junctions. A vehicle can only move along a road when the traffic light at the current junction is green. If a vehicle arrives when the light is not green, it must wait until the next green flash.

The goal is to determine the minimum time required to travel from a given source junction ‘src’ to a destination junction ‘des’ using the given map, which includes the travel times for all roads and the green light period ‘P[i]’ for each junction ‘i’.

Input:

The first line contains a single integer ‘T’ representing the number of test cases.
Each test case includes the following:
- Two space-separated integers, ‘N’ and ‘M’, representing the number of junctions and roads.
- ‘N’ space-separated integers denoting the green light period array ‘P’ where ‘P[i]’ is the time needed at junction ‘i’.
- ‘M’ lines, each containing three space-separated integers denoting a road between junction ‘Edges[i][0]’ and junction ‘Edges[i][1]’ with travel time ‘Edges[i][2]’.
- Two space-separated integers, ‘src’ and ‘des’, indicating the source and destination junctions.

Output:

For each test case, output a single integer representing the minimum time needed from ‘src’ to ‘des’. Output ‘-1’ if ‘des’ is unreachable.

Example:

Consider ‘N’ = 3 with edges:
[[0, 1, 2],
 [1, 2, 4]]
‘P’ = [2, 3, 4], from 0 to 2.
The path 0 -> 1 -> 2 takes time 2 + 1 (wait) + 4 = 7.
Hence, the answer is 7.

Constraints:

• 1 ≤ T ≤ 5
• 2 ≤ N ≤ 105
• 1 ≤ M ≤ 105
• 1 ≤ P[i] ≤ 107
• 0 ≤ Edges[i][0], Edges[i][1] < N
• 1 ≤ Edges[i][2] ≤ 107
• 0 ≤ src, des < N
• Time limit: 1 sec