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 $d i s t (x, y)$ equals $s_y$ — where $d i s t (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 <= n <= 2 times 10^5,$ $0 <= m <= 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 <= s_i <= 10^(15))$.
The following $m$ lines contain information about the edges. Each line contains three integers $u_i$, $v_i$, and $w_i$ $(1 <= w_i <= 10^9,$ $u_i eq.not 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.
## Input
The first line contains two integers $n$ and $m$ $(1 <= n <= 2 times 10^5,$ $0 <= m <= 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 <= s_i <= 10^(15))$.The following $m$ lines contain information about the edges. Each line contains three integers $u_i$, $v_i$, and $w_i$ $(1 <= w_i <= 10^9,$ $u_i eq.not v_i)$.Note that our graph is a good graph. Good graphs do not contain loops or multiple edges.
## Output
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.
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case $ i \in \{1, \dots, T\} $:
- Let $ n_i \in \mathbb{Z} $ be the number of design points.
- Let $ k_i \in \mathbb{Z} $ be the number of pairs to select.
- Let $ P_i = (p_{i,1}, p_{i,2}, \dots, p_{i,n_i}) $ be a sequence of real numbers representing coordinates on the number line.
**Constraints**
1. $ 1 \le T \le 100 $
2. For each $ i \in \{1, \dots, T\} $:
- $ 2 \le n_i \le 2 \times 10^5 $
- $ 1 \le k_i \le \left\lfloor \frac{n_i}{2} \right\rfloor $
- $ |p_{i,j}| \le 10^9 $ for all $ j \in \{1, \dots, n_i\} $
3. $ \sum_{i=1}^{T} n_i \le 10^6 $
**Objective**
For each test case $ i $:
- Sort $ P_i $ in non-decreasing order: $ p_{i,(1)} \le p_{i,(2)} \le \dots \le p_{i,(n_i)} $.
- Select exactly $ k_i $ **disjoint** pairs of points (each point used at most once).
- Define the value of a pair $ (p_a, p_b) $ as $ |p_a - p_b| $.
- Compute:
- $ y_i $: minimum possible total value of $ k_i $ pairs.
- $ z_i $: maximum possible total value of $ k_i $ pairs.
**Output**
For each test case $ i $, output:
$$ \text{Case \#}i: y_i\ z_i $$