Minimum Travel Cost to Maximum Supplies Safe House

You are given a set of safe houses and bidirectional paths connecting them. Each safe house has a certain number of supplies. Your task is to find the minimum travel cost from safe house 1 to any safe house that contains the maximum number of supplies.

The problem can be formulated as follows:

Let \(N\) be the number of safe houses and \(E\) the number of bidirectional paths. Each safe house \(i\) (where \(1 \le i \le N\)) contains \(s_i\) supplies and each path is described by three integers \(u, v, c\) representing a connection between safe houses \(u\) and \(v\) with a travel cost \(c\). Compute the minimum cost required to reach a safe house that has the maximum supplies.

If there is no way to reach a safe house with the maximum supplies from safe house 1, print inf.

Note: The safe houses are labelled from 1 to \(N\), and the paths are undirected. In other words, if there is a path between safe house \(u\) and safe house \(v\), it can be traversed in both directions.

inputFormat

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

N E
s1 s2 ... sN
u1 v1 c1
u2 v2 c2
... 
 uE vE cE

• The first line contains two integers \(N\) and \(E\), where \(N\) is the number of safe houses and \(E\) is the number of paths.
• The second line contains \(N\) space-separated integers representing the supplies for each safe house (from safe house 1 to safe house N).
• Each of the next \(E\) lines contains three integers \(u, v, c\), where \(u\) and \(v\) denote the indices of the connected safe houses and \(c\) is the travel cost between them.

outputFormat

Output a single line to stdout containing the minimum travel cost to reach a safe house with the maximum supplies. If no such house is reachable, output inf.

## sample

6 7
10 20 30 10 20 30
1 2 5
1 3 10
2 3 5
2 4 10
3 5 5
4 6 5
5 6 10

10