给出一组包含 \(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;
}