You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

新能源车好啊，听说上牌都比燃油车简单。

沙东省济北市，齐鲁大地上的一颗文化明珠。

某天，你听说在济北市购买新能源汽车质量很好，能免费上牌照，还可以自由选择车牌号！欣喜之余，来自沙东省济北市的你，打算买一辆新能源车。

作为沙东省省会城市的济北市，现在已经是响当当的“文明城市”了。因此，济北市推出的「超严格环保条例」你也需要遵守啦~

题目描述

你来到了 4s 店。你发现，对于一辆新能源汽车，其排污量可以用一个介于 $(-\infty,+\infty)$ 内的整数 $p$ 表示。

另一方面，济北市由 $n$ 个区县和 $m$ 条双向道路组成。最新的「超严格环保条例」为连接各区县的道路设置一个排污上限 $e_i$。当某辆车的排污量 $p>e_i$ 时，则该车不允许通过这条道路。

你很担心自己买了车却无法在济北市四处乱窜。于是，你打算对济北市的整体情况做个调查。我们定义区县 $i$ 的环境严格指数为 $s_i$。$s_i$ 定义如下

其中 $\mathbb{Z}$ 表示整数集，$w(i,q)$ 的意义如下：

• 设从区县 $i$ 出发，开着一辆排污量为 $q$ 的车能到达济北市的 $a$ 个区县；
• 设从区县 $i$ 出发，开着一辆排污量为 $q+1$ 的车能到达济北市的 $b$ 个区县；
• 则 $w(i,q)=(a-b)^2$ 。

现在你想知道：每个区县的环境严格指数 $s_i$ 分别是多少呢？

输入格式

第 $1$ 行包含两个正整数 $n, m$，分别表示区县数及道路数。

第 $2\sim m + 1$ 行，每行三个正整数 $u_i,v_i,e_i$，表示一条道路连接的两端的区县编号，以及这条道路的排污上限。

输出格式

共一行 $n$ 个整数，为每个区县的环境严格指数。

3 2
1 2 1
2 3 2

4 2 2

输入数据2

见样例文件 ex.in

输出数据2

见样例文件 ex.out

数据范围

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

对于 $50\%$ 的数据，满足 $1\leq n \leq 1000$，$1\leq m \leq 2\times 10^4$。

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

对于 $100\%$ 的数据，满足 $1 \leq n \leq 10^5$，$1 \leq m \leq 5\times 10^5$，$0\leq e_i\leq 10^7$。