N. 铁路建设
时间限制：每个测试点 $4$ 秒
内存限制：每个测试点 $1024$ MB

Truckski 国家地处崎岖多山的地区，地质条件引发了各种各样的问题。崎岖的地形将国家中不同的州分隔开来，导致州际通勤极为不便，更重要的是中央政府无法有效掌控全局。再加上逐年上升的犯罪率，这严重影响了无辜公民的日常生活。

最近的一场抗议活动终于使情况得到关注，新任总统宣布了一项雄心勃勃的计划来解决这些问题。她的计划包含两个主要部分。
第一部分是在各州之间修建高速铁路，以促进全国范围内更好的连接和团结。由于各州基本上各自独立运行，要在州 $u$ 和州 $v$ 之间修建铁路，政府需要支付 $a_u + a_v$ 美元的费用，其中 $a_u$ 美元付给州 $u$，$a_v$ 美元付给州 $v$。铁路是双向运行的，一旦建成，州 $u$ 的居民就可以前往州 $v$，反之亦然。除了 $m$ 个特定的州对之外，几乎任何一对州之间都可以修建铁路——这 $m$ 对州之间的地形极其险恶，无法直接修建铁路。

该项目的第二部分是建造一个中央监狱，关押全国所有罪犯。考虑到预计的囚犯数量很大，总统决定选择一个州来建造中央监狱，并切断该州与全国其他地区的联系。

给定以上条件，总统希望找到修建铁路的最小成本方案，使得：

• 建有中央监狱的州不应有任何铁路连接到其他州，并且
• 其他所有州之间应相互连通，即人们可以从一个这样的州通过乘坐多次火车到达另一个这样的州。

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

输入
第一行包含两个整数 $n$ 和 $m$，分别表示 Truckski 的州的数量和无法修建直接铁路的州的对数。
接下来一行包含 $n$ 个整数 $a_1, \dots, a_n$，表示政府需要支付给第 $i$ 个州的费用。
然后 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$，表示不能在州 $u_i$ 和 $v_i$ 之间修建直接铁路。

数据范围：

• $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 \ne j$，有 $(u_i, v_i) \ne (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