Description

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

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

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

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

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

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

Input Format

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

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

Output Format

输出一行共 $n$ 个整数，为每个城市的环境严格指数。

3 2
  1 2 1
  2 3 2

4 2 2

输入数据2

见样例文件 ex.in

输出数据2

见样例文件 ex.out

Constraints

对于 $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$。