Truckski 国位于一个崎岖多山的地区，地质条件引发了诸多问题。险峻的地形将国家的不同联邦州隔离开来，导致州际通勤极其不便，更关键的是缺乏中央政府的控制。此外，犯罪率逐年上升，严重干扰了无辜公民的日常生活。

最近的一次抗议终于让情况引起了关注，新当选的总统宣布了一项雄心勃勃的计划来解决这些问题。她的计划由两个主要部分组成。第一部分是在各州之间建设高速铁路，以促进全国更好的连接和统一。由于各州大多独立运行，要在州 $u$ 和州 $v$ 之间建设一条铁路，政府必须支付 $a_u + a_v$ 美元的费用，其中 $a_u$ 美元给州 $u$，$a_v$ 美元给州 $v$。铁路是双向运行的，这意味着一旦建成，州 $u$ 的居民就可以前往州 $v$，反之亦然。几乎任意两州之间都可以建设铁路，除了 $m$ 对特定的州，由于它们之间的地形过于险恶，无法在它们之间建设直达铁路。

项目的第二部分是建立一个集中式监狱，管理全国的所有罪犯。鉴于预计的囚犯数量庞大，总统决定选择其中一个州来建造中央监狱，并切断该州与国家其他地区的联系。

样例输入 1 的示意图。(a) 在各州之间建设直达铁路的成本。(b) 考虑在 3 号州建造中央监狱。必须建设所有不涉及 3 号州的直达铁路，总成本为 $3 + 3 + 2 = 8$ 美元。

鉴于上述情况，总统希望寻找一个建设州际铁路的最小成本方案，使得：

• 建造了中央监狱的州不应有任何铁路与其他任何州相连，且
• 所有其他州都应该是连通的，即人们应该能够从一个这样的州旅行到另一个州，可能需要换乘多次火车。

你正在为负责整体建设规划的团队工作。与总统的会议将在几个小时内举行，届时你必须向她简要汇报不同建设方案的成本。请计算，对于每个州 $u$，当 $u$ 是建造中央监狱的州时，满足上述条件的建设州际铁路的最小成本方案。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$，分别表示 Truckski 国的州数和无法建设铁路的州对数。

下一行包含 $n$ 个整数 $a_1, \dots, a_n$，表示政府需要支付给第 $i$ 个州的建设费用。

接下来 $m$ 行。第 $i$ 行包含两个整数 $u_i$ 和 $v_i$，表示无法在州 $u_i$ 和 $v_i$ 之间建设（直达）铁路。

输出格式

在一行中输出 $n$ 个整数。第 $i$ 个整数表示当第 $i$ 个州建造监狱时的最小建设成本。如果无法找到可行的铁路建设方案，则输出 -1。

数据范围

• $2 \le n \le 10^5$
• $0 \le m \le 10^5$
• $1 \le a_i \le 10^9$
• $1 \le u_i < v_i \le n$
• 对于所有 $i \neq j$，$(u_i, v_i) \neq (u_j, v_j)$。

样例

输入样例 1

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

输出样例 1

7 6 8 7 7

输入样例 2

3 2
1 2 3
1 2
2 3

输出样例 2

-1 4 -1