求条模板题

#include<bits/stdc++.h>

namespace IO {
	inline int read() {
		int ret = 0, f = 1;char ch = getchar();
		while (ch < '0' || ch > '9') {
			if (ch == '-') f = -f;
			ch = getchar();
		}
		while (ch >= '0' && ch <= '9') {
			ret = (ret << 1) + (ret << 3) + (ch ^ 48);
			ch = getchar();
		}
		return ret * f;
	}
	void write(int x) {
		if (x < 0) putchar('-'), x = -x;
		if (x > 9) write(x / 10);
		putchar(x % 10 + '0');
	}
} 

using namespace IO;
using namespace std;

const int maxn = 5e3 + 5;
const int maxm = 5e3 + 5;

int tot, to[maxm], nxt[maxm], head[maxn], val[maxm];
void add(int u, int v, int c) {
	tot++;
	nxt[tot] = head[u];
	head[u] = tot;
	to[tot] = v;
	val[tot] = c;
}

int n, m;
//typedef pair<int, int> PII;

queue<int> q;
int dis[maxn], vis[maxn], ex[maxn];
void SPFA() {
	memset(dis, 0x7f, sizeof(dis));
	q.push(m + 1), vis[m + 1] = 1, dis[m + 1] = 0;
//	for (int i = 1;i <= n;i++) q.push(i), vis[i] = 1;
	while (!q.empty()) {
		int now = q.front();q.pop();
		vis[now] = 0;
		for (int i = head[now];i;i = nxt[i]) {
			int v = to[i], Val = val[i];
//			cout << v << ' ' << Val << ' ' << dis[now];
			if (dis[now] + Val < dis[v]) {
				dis[v] = dis[now] + Val;ex[v] = ex[now] + 1;
				if (ex[v] == n) {
					puts("NO");
					exit(0);
				}
				if (!vis[v]) vis[v] = 1, q.push(v);
			}
		}
	}
}

int main() {
	n = read(), m = read();
	for (int i = 1;i <= m;i++) {
		int a = read(), b = read(), c = read();//a - b <= c
		add(b, a, c);
	}
	
	for (int i = 1;i <= n;i++) add(m + 1, i, 0); 
	for (int i = head[0];i;i = nxt[i]) cout << to[i] << ' ' << val[i] << '\n';
	SPFA();
	
	for (int i = 1;i <= n;i++) write(dis[i]), putchar(' ');
	return 0;
}