这题看着很吓人实则很简单。求输出层，正着求很麻烦，因为知不道谁连向这个点，所以可以反向建边，反着求。
拓扑+dfs，时间复杂度 \(\text{O(n + m)}\)
#include <iostream>
#include <cstdio>
#include <queue>
#define N 105
#define M (N * N / 2 + 114)
struct E {
int v, w;
int nxt;
} e[M];
int hed[N], cnt;
void add_edge(int u, int v, int w) {
e[++cnt] = {v, w, hed[u]};
hed[u] = cnt;
}
int C[N], U[N];
int n, m;
int indeg[N];
bool vis[N];
int dfs(int k) {
if(vis[k])
return C[k] > 0 ? C[k] : 0;
vis[k] = 1;
if(hed[k] == 0)
return C[k] > 0 ? C[k] : 0;
int res = 0;
for(int i = hed[k]; i; i = e[i].nxt)
{
int v = e[i].v;
res += dfs(v) * e[i].w;
}
C[k] = res - U[k];
return C[k] > 0 ? C[k] : 0;
}
signed main() {
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++)
scanf("%d %d", &C[i], &U[i]);
for(int i = 1, u, v, w; i <= m; i++)
{
scanf("%d %d %d", &u, &v, &w);
add_edge(v, u, w);
indeg[u]++;
}
for(int i = 1; i <= n; i++)
if(indeg[i] == 0)
dfs(i);
bool flag = true;
for(int i = 1; i <= n; i++)
if(C[i] > 0 && indeg[i] == 0)
flag = false;
if(flag) {
puts("NULL");
return 0;
}
for(int i = 1; i <= n; i++)
if(C[i] > 0 && indeg[i] == 0)
printf("%d %d\n", i, C[i]);
return 0;
}