Maximum Simple Path Weight

You are given an undirected graph with \(n\) vertices and \(m\) edges. Each vertex \(i\) (1-indexed) is assigned a positive integer weight \(w_i\). A simple path in the graph is a path that does not pass through any vertex more than once. The weight of a simple path is defined as the sum of the weights of the vertices along the path, i.e., for a path with vertices \(i_1, i_2, \ldots, i_k\), its weight is \(w_{i_1}+w_{i_2}+\cdots+w_{i_k}\).

Your task is to compute, for each vertex, the maximum possible weight of any simple path starting from that vertex.

Note: Since finding the longest simple path is an NP-hard problem in the general case, you may assume the graph size in the input is small enough to allow a complete search.

inputFormat

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

 n m
 w₁ w₂ ... wₙ
 u₁ v₁
 u₂ v₂
 ...
 uₘ vₘ

Here, the first line contains two integers \(n\) and \(m\) representing the number of vertices and edges respectively. The second line contains \(n\) integers, where the \(i\)th integer represents the weight \(w_i\) of the \(i\)th vertex. Each of the next \(m\) lines contains two integers \(u\) and \(v\) (1-indexed), indicating an undirected edge connecting vertices \(u\) and \(v\>.

outputFormat

Output a single line (via stdout) with \(n\) space-separated integers. The \(i\)th integer should represent the maximum weight of any simple path starting from vertex \(i\) (1-indexed).

## sample

4 4
10 20 30 40
1 2
2 3
3 4
4 2

100 90 70 40

</p>