特拉斯基国家位于崎岖的山区,地质条件引发了一系列问题。具有挑战性的地形将该国不同的州分开,导致州际通勤极其不便,更重要的是缺乏中央政府的控制。除此之外,犯罪率逐年上升,严重扰乱了无辜公民的日常生活。
最近的抗议活动终于揭示了情况,因为新当选的总统宣布了一项雄心勃勃的项目来解决这些问题。她的计划由两个主要部分组成。首先是建设州际高速铁路,以促进全国各地更好的联系和团结。由于各州大多彼此独立运行,要在 $$$u$$$ 州和 $$$v$$$ 州之间修建铁路,政府必须支付 $$$a_u + a_v$$$ 美元的费用,其中 $$$a_u$$$ 美元给州 $$$u$$$,$$$a_v$$$ 美元给州 $$$v$$$。该铁路是双向运营的,这意味着一旦建成,来自 $$$u$$$ 州的人们现在可以前往 $$$v$$$ 州,反之亦然。几乎任何两个州之间都可以修建铁路,但有一些特定的州除外,因为它们之间的地形非常危险,以至于在两个州之间修建直达铁路是不可能的。
该项目的第二个组成部分是建立一个集中监狱,管理全国所有的罪犯。鉴于估计囚犯人数众多,总统决定选择其中一个州建造中央监狱,并切断该州与全国其他地区的联系。
示例输入 1 的说明。(a) 在各州之间修建直达铁路的成本。 (b) 考虑在#3 州建造中央监狱。必须修建所有不涉及第 3 州的直达铁路,总成本为 $$$3+3+2=8$$$ 美元。
鉴于上述情况,总统希望寻找在各州之间建设铁路的最低成本计划,以便:
- 有中央监狱的州不应有任何铁路将其连接到任何其他州,并且
- 所有其他州都应该连接起来,即人们应该能够从一个这样的州前往另一个州,可能需要乘坐多趟火车。
您在负责施工总体规划的团队工作。几个小时后就要与总统会面,届时您必须向她介绍不同建设计划的成本。请计算每个州$$$u$$$在$$$u$$$为中央监狱所在地时,满足上述条件的州之间修建铁路的最低成本计划。
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$,即 Truckski 中的州数以及铁路建设不可行的对数。下一行包含$$$n$$$整数$$$a_1,\ldots,a_n$$$,政府需要向第$$$i$$$个州支付的建设费。然后是 $$$m$$$ 行。第 $$$i$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ 意味着不可能在 $$$u_i$$$ 州和 $$$v_i$$$ 州之间修建(直接)铁路。
- $$$2\leq n\leq 10^5$$$
- $$$0\leq m\leq 10^5$$$
- $$$1\leq a_i\leq 10^9$$$
- $$$1\leq u_i<v_i\leq n$$$
- 对于所有$$$i\neq j,(u_i, v_i)\neq (u_j, v_j)$$$。
输出
在一行中输出 $$$n$$$ 个整数。第 $$$i$$$ 个整数是当第 $$$i$$$ 个州是建造监狱时的最低建设成本。如果无法找到可行的铁路建设,则输出-1。
示例
输入 #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