给出一组包含 $m$ 个不等式，有 $n$ 个未知数的形如：

$$ \begin{cases} x_{c_1}-x_{c’1}\leq y_1 \x{c_2}-x_{c’2} \leq y_2 \ \cdots\ x{c_m} - x_{c’_m}\leq y_m\end{cases}$$

的不等式组，求任意一组满足这个不等式组的解。

输入格式

第一行为两个正整数 $n,m$，代表未知数的数量和不等式的数量。

接下来 $m$ 行，每行包含三个整数 $c,c’,y$，代表一个不等式 $x_c-x_{c’}\leq y$。

数据范围

对于 $100%$ 的数据，$1\leq n,m \leq 5\times 10^3$，$-10^4\leq y\leq 10^4$，$1\leq c,c’\leq n$，$c \neq c’$。

#define MAXN 5005
#define MAXM 10005
using namespace std;
int read()
{
    int ans = 0, sgn = 1;
    char c = getchar();
    while (!isdigit(c))
    {
        if (c == '-')
            sgn *= -1;
        c = getchar();
    }
    while (isdigit(c))
    {
        ans = ans * 10 + c - '0';
        c = getchar();
    }
    return ans * sgn;
}
int cnt_edge, head[MAXN];
struct
{
    int to, next, w;
} edges[MAXM];
void add_edge(int from, int to, int w)
{
    edges[++cnt_edge].next = head[from];
    edges[cnt_edge].to = to;
    edges[cnt_edge].w = w;
    head[from] = cnt_edge;
}
bool inqueue[MAXN];
int cnt[MAXN], dis[MAXN];
queue<int> Q;
bool SPFA(int s, int n)
{
    memset(dis, 127, sizeof(dis));
//  memset(dis, -127, sizeof(dis));
    dis[s] = 0;
    Q.push(s);
    while (!Q.empty())
    {
        int p = Q.front();
        if (cnt[p] > n)
            return false;
        Q.pop();
        inqueue[p] = false;
        for (int eg = head[p]; eg != 0; eg = edges[eg].next)
        {
            int to = edges[eg].to;
            if (edges[eg].w + dis[p] < dis[to])
//          if (edges[eg].w + dis[p] > dis[to])
            {
                dis[to] = edges[eg].w + dis[p];
                if (!inqueue[to])
                {
                    Q.push(to);
                    inqueue[to] = true;
                    cnt[to]++;
                }
            }
        }
    }
    return true;
}
int main()
{
    int n = read(), m = read();
    for (int i = 0; i < m; ++i)
    {
        int x = read(), y = read(), w = read();
        add_edge(y, x, w);
//      add_edge(x, y, -w);
    }
    for (int i = 1; i <= n; ++i)
        add_edge(0, i, 0);
    if (SPFA(0, n))
    {
        for (int i = 1; i <= n; ++i)
            printf("%d ", dis[i]);
    }
    else
        puts("NO");
    return 0;
}