题目描述

给定 $n$ 个未知整数 $x_1,x_2,\dots,x_n$ 以及 $m$ 条形如

的约束，请你求出一组满足全部约束的整数解；如果不存在这样的解，请输出无解。

为了让所有正确程序输出一致，本题额外规定：解必须满足所有 $x_i\le 0$，并且在此前提下每个 $x_i$ 都取到尽可能大的值（可以证明这样的解如果存在就是唯一的）。

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行，每行三个整数 $u,v,w$，表示约束 $x_v-x_u\le w$。

输出格式

若存在满足要求的解，输出一行 $n$ 个整数，依次为 $x_1,x_2,\dots,x_n$，相邻两个整数之间用一个空格隔开。

若无解，输出一行 NO。

输入输出样例 #1

输入 #1

3 3
1 2 -1
2 3 3
3 1 -1

输出 #1

-1 -2 0

说明

数据范围

• 对于 $100\%$ 的数据，$1\le n\le 10^5$，$0\le m\le 2\times 10^5$，$|w|\le 10^6$。答案中每个数的绝对值不会超过 $10^{11}$。