给出一组包含 mm 个不等式，有 nn 个未知数的形如：

{xc1−xc1′≤y1xc2−xc2′≤y2⋯xcm−xcm′≤ym\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,mn,m，代表未知数的数量和不等式的数量。

接下来 mm 行，每行包含三个整数 c,c′,yc,c',y，代表一个不等式 xc−xc′≤yx_c-x_{c'}\leq y。

数据范围

对于 100%100\% 的数据，1≤n,m≤5×1031\leq n,m \leq 5\times 10^3，−104≤y≤104-10^4\leq y\leq 10^4，1≤c,c′≤n1\leq c,c'\leq n，c≠c′c \neq c'。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#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;
}