Migrated from Lutece 2933 信软社交王

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

在小小的沙河校区，只要你足够社牛，你甚至可以认识所有人！

沙软同学们的社交关系可以视为 $n$ 个点 $m$ 条边的无向连通图。每一条边有一个权值 $w_i$ 连接两个同学 $x_i$ 和 $y_i$ ，权值表示两人的生疏程度，每个人有一个社交能力值 $a_i$ 。

我们假设只有一个同学主动去交朋友，其他同学不会去主动交朋友。开学时这位同学只认识自己，ta认识一位新朋友需要以下条件：

1、ta还不认识这位同学，但是这位同学和ta认识的某个朋友有一条连边。

2、ta目前认识的所有朋友的社交能力值之和大于等于这条连边的权值，说明ta可以通过朋友的力量认识一个新同学。

这个主动交朋友的同学会一直以这种方式去认识新朋友，直到无法找到新朋友。

请你计算出每一个人主动去交朋友的话，在无法找到新朋友后，ta认识的所有人当中社交能力小于他的有多少人，社交能力大于他的有多少人（相等不计入答案）。

（每位同学的计算过程互不影响，每计算完一个同学后时间会自动回到开学前）

Input

第一行输入两个整数 $n$, $m$，表示人数和边数。

第二行输入 $n$ 个整数， $a_i$ 表示第 $i$ 位同学的社交能力值。

接下来的 $m$ 行每行输入三个整数，第 $i$ 行输入的三个数 $x_i$，$y_i$ 和 $w_i$，表示一条边连接的两个同学的编号和这条边的边权。（数据保证连通，没有自环）

Output

输出有 $n$ 行，第 $i$ 行两个整数表示如果开学只有 $i$ 同学主动去交朋友， ta可以认识的人当中，社交能力小于ta和大于ta的人的数量。

Samples

4 4
4 5 3 7
1 2 4
2 3 10
3 4 5
4 1 100

0 1
1 0
0 0
3 0

Constraints

$1 \leq n, m \leq 1 \times 10^5$，$1 \leq x_i , y_i \leq n$，$1 \leq a_i , w_i \leq 1 \times 10^9$。

Note

样例解释： 1同学可以认识2，1和2加起来能力值小于10，无法认识3。 2同学可以认识1。 3同学无法认识任何人。 4同学可以先认识3，然后4和3能力值加起来大于等于10，可以认识2，三人的值大于4，可以认识1。

对此题算法不太熟悉的同学，可以先通过我们B站的UESTC-ICPC官方账号来学习：成电算法讲堂（图论篇）

Resources

2023 UESTC ICPC Training for Graph