Minimal Toll for Islands with Equal Defense

You are given a set of N islands, each having a defense value. The islands are connected by M bidirectional bridges, each with an associated toll cost. Your task is to determine the minimum toll required to travel between any two islands that share the same defense value.

Formally, let \(N\) be the number of islands, and let the defense values be \(d_1, d_2, \dots, d_N\). There are \(M\) bridges where each bridge connects two islands \(u\) and \(v\) with a toll cost of \(w\). You need to find two islands \(i\) and \(j\) such that \(d_i = d_j\) and the sum of the toll costs along the path from \(i\) to \(j\) is minimized. If no such pair exists or the islands are not connected, output -1.

Input Constraints:

• All islands are numbered from 1 to \(N\).
• The graph may not be fully connected.

Note: If there are multiple paths between a pair of islands, choose the one with the minimum total toll cost, which is given by:

[ \text{Toll}(P) = \sum_{(u,v) \in P} w_{uv} ]

where \(P\) denotes a path from one island to another.

inputFormat

The input is given via standard input (stdin) in the following format:

N
d1 d2 ... dN
M
u1 v1 w1
u2 v2 w2
...
uM vM wM

Where:

• N is the number of islands.
• The second line contains N space-separated integers representing the defense values of the islands.
• M is the number of bridges.
• Each of the next M lines contains three integers: u v w, denoting a bridge between island u and island v with a toll cost w.

outputFormat

The output should be a single integer printed on standard output (stdout) representing the minimal toll required to travel between any two islands that have the same defense value. If no such pair exists, print -1.

## sample

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

4