#5149. 云斗杯.十月赛 CSP-S 复赛模拟 D. 小花的环境治理

云斗杯.十月赛 CSP-S 复赛模拟 D. 小花的环境治理

Description

S 省由 nn 个城市和 mm 条道路组成。某天你听说 S 省的新能源汽车质量很好。于是你打算到 S 省买辆新能源车。

你发现一两新能源汽车的排污量可以用一个介于 (,+)(-\infty,+\infty) 内的整数 pp 表示。当你正犹豫时,你发现店里电视上正在播出 S 省环境治理署的署长小花宣布了 S 省的新的通行政策:为省内连接各城市的道路设置一个排污上限 eie_i。当某辆车的排污量 p>eip>e_i 时,则该车不允许通过这条道路

你很担心自己买完了车却开不出 S 省。于是你打算对 S 省整体情况做个调查。我们定义城市 ii 的环境严格指数为 sis_isis_i 定义如下

si=p=,pZr(i,p)s_i=\sum_{p=-\infty,p\in \mathbb{Z}}^{\infty} r(i,p)

其中 Z\mathbb{Z} 表示整数集。r(i,p)r(i,p) 的意义为,若当从城市 ii 出发开着一辆排污量为 pp 的车时能达到 S 省的 xx 个城市,而若从城市 ii 出发开着一辆排污量为 p+1p+1 的车时能达到 S 省的 yy 个城市时,r(i,p)=(xy)2r(i,p)=(x-y)^2

现在你需要知道每个城市的环境严格指数 sis_i 分别是多少。

Input Format

输入文件第一行为两个正整数 n,mn, m,分别表示城市数及道路数。

接下来 mm 行,每行三个正整数 ui,vi,eiu_i,v_i,e_i,表示一条道路连接的两端的城市的编号,以及这条道路的排污上限。u,v1nu,v\in 1\sim n

Output Format

输出一行共 nn 个整数,为每个城市的环境严格指数。

3 2
  1 2 1
  2 3 2
4 2 2

输入数据2

见样例文件 ex.in

输出数据2

见样例文件 ex.out

Constraints

对于 30%30\% 的数据,满足 1n,m1001\leq n,m\leq 100

对于 50%50\% 的数据,满足 1n10001\leq n \leq 10001m2×1041\leq m \leq 2\times 10^4

对于另 20%20\% 的数据,输入数据保证任意两条边的排污上限互不相等。

对于 100%100\% 的数据,满足 1n1051 \leq n \leq 10^51m5×1051 \leq m \leq 5\times 10^50ei1070\leq e_i\leq 10^7