407719: GYM102881 H Shortest Array

Pillow is well known for being unexpected, so while all the students were amazed by how you can get the shortest path to all nodes in a graph in polynomial time, Pillow was asking himself: "If I know the shortest path from a node to all the other nodes, can I get that node?".

Formally, you are given a connected graph $$$g$$$ with edges of positive weights, and an array $$$s$$$. You are asked to find a node $$$x$$$ such that $$$dist(x, y)$$$ equals $$$s_y$$$ — where $$$dist(x, y)$$$ is the the length of the shortest path between vertices $$$x$$$ and $$$y$$$ in $$$g$$$.

Yassora, a role model student, asked Pillow: "Wouldn't that be the node $$$y$$$ such that $$$s_y=0$$$?".

Pillow, surprised from the naivety of that question, told Yassora that life wasn't that easy, so he decided that a shortest path needs to consist of at least one move, making Yassora utter the words: "Outstanding Move".

The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n \leq 2 \times 10^5,$$$ $$$0 \leq m \leq 2 \times 10^5)$$$ — the number of nodes and the number of edges in the graph.

The second line contains $$$n$$$ space-separated integers denoting the array $$$s$$$ $$$(1 \leq s_i \leq 10^{15})$$$.

The following $$$m$$$ lines contain information about the edges. Each line contains three integers $$$u_i$$$, $$$v_i$$$, and $$$w_i$$$ $$$(1 \leq w_i \leq 10 ^ 9,$$$ $$$u_i \neq v_i)$$$.

Note that our graph is a good graph. Good graphs do not contain loops or multiple edges.

If there's no node that generates this shortest path array, print "-1". Otherwise, print the smallest indexed node that generates this shortest path array.

4 4
6 3 6 6
1 3 6
1 2 3
3 2 3
4 2 3

1

4 4
6 3 4 8
1 3 4
1 2 3
2 4 5
3 4 4

1

5 6
8 4 4 8 6
1 2 4
1 3 4
2 4 4
3 4 4
1 5 3
5 3 2

4