跳蚤国由 $n$ 个城市组成，编号为 $1$ 到 $n$。

跳蚤国有 $m$ 条连接城市的单向高速公路。经过高速公路当然是要收费的 —— 每条高速公路都有一个过路费 $w$ （货币单位为跳蚤币），司机每次经过这条公路时都需要缴纳 $w$ 跳蚤币。特别地，过路费可以是负的，这表示司机每次经过这条公路时政府都会给 $-w$ 跳蚤币的补贴。

随着时代发展，跳蚤国王认为原有的高速公路规划已经不符合国情了。于是他根据交通拥堵情况把每条公路染成了红、绿、白三色之一，然后他会小心地选定一个数 $x$，再把每条红色公路的过路费涨 $x$ 跳蚤币，把每条绿色公路的过路费降 $x$ 跳蚤币，而白色公路的过路费不变。

虽然让绿色公路降过路费是好事，但是如果过路费降得太厉害，某个跳蚤司机就可以从 $1$ 号城市出发在城市间转悠，最后停在某个城市 $v$，数一下自己的钱包发现自己竟然赚钱了。如果赚的钱超过 $10^{100}$ 跳蚤币，则我们称这样的路径为发财路径。

现在跳蚤国王还不太确定 $x$ 的取值应该是多少，他当然讨厌这种丑陋的靠补贴费发财的行为。于是他希望助手伏特对于 $v = 1 \dots n$，求出使得不存在从 $1$ 号城市出发到 $v$ 号城市结束的发财路径的整数 $x$ 的个数。

除此之外，$x$必须介于 $-10^{30}$ 到 $10^{30}$之间。

伏特当然知道怎么做啦！但是他想考考你。

输入格式

第一行包括两个正整数 $n$ 和 $m$。表示跳蚤国的城市数和高速公路数。

接下来 $m$ 行，每行四个用空格隔开的整数 $v, u, w, s$ （$1 \leq v, u \leq n$， $s \in \{-1, 0, 1\}$），表示一条从 $v$ 号城市向 $u$ 号城市的过路费为 $w$ 的单向高速公路。如果 $s = 1$ 则为红色，$s = 0$ 则为白色，$s = -1$ 则为绿色。

输出格式

输出 $n$ 行，第 $i$ 行包含一个整数表示 $v = i$ 时满足条件的 $x$ 的个数。如果 $x$ 的个数超过 $10^{18}$个，请输出 $-1$。

C/C++ 输入输出 long long 时请用 %lld。C++ 可以直接使用 cin/cout 输入输出。

样例一

input

5 6
1 2 7 0
1 4 3 -1
2 5 4 0
2 3 1 -1
2 3 -3 1
3 2 1 0

output

-1
1
1
-1
1

explanation

对于任何一个 $x$ 都找不到从 $1$ 出发到 $1, 4$ 结束的发财路径。

只有当 $x = 2$ 时，才找不到从 $1$ 出发到 $2, 3, 5$ 结束的发财路径。

样例二

input

12 15
1 2 1 0
1 4 1000000000 0
1 6 2 0
2 3 2 0
4 4 -2 1
4 4 10 -1
4 3 1000000000 0
6 7 -5 0
7 8 10 -1
8 6 10 -1
7 9 6 -1
9 10 2 1
10 11 3 1
11 9 5 1
12 12 -233 0

output

-1
-1
9
9
-1
-1
-1
-1
11
11
11
-1

explanation

对于 $3, 4$ 号城市，无法发财的 $x$ 的取值范围为 $[2, 10]$。

对于 $6, 7, 8$ 号城市，无法发财的 $x$ 的取值范围为 $[-10^{30}, 7.5]$。

对于 $9, 10, 11$ 号城市，无法发财的 $x$ 的取值范围为 $\left[-\frac{10}{3}, 7.5\right]$。由于要求是整数，所以只有介于 $-3$ 到 $7$ 的整数满足条件，共 $11$ 个 $x$ 的取值。

特别注意 $12$ 号城市，虽然不断地从 $12$ 号城市出发再回 $12$ 号城市就可以发财，但是 $1$ 号城市无法到达 $12$ 号城市，所以所有 $x$ 都满足条件。

样例三

见样例数据下载。去掉所有的自环后图中不存在环。

样例四

见样例数据下载。

限制与约定

保证对于每条边，$\left|w \right| \leq 10^9$。

时间限制：$1\texttt{s}$

空间限制：$256\texttt{MB}$

下载

样例数据下载