记录编号	98764	评测结果	AAAAAAAAA
题目名称	工程规划	最终得分	100
用户昵称	OI永别	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2014-04-24 17:21:03	内存使用	0.38 MiB

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 1010
#define M 5011
#define INF 0x3f3f3f3f
struct arr{
	int ff,tt,ww;
}c[M];
int dis[N];
int tot = 0;
bool flag = 0;
inline void add(int x,int y,int z){
	c[++tot].ff = x;
	c[tot].tt = y;
	c[tot].ww = z;
	return;
}
int n,m;
bool bellman_ford(){
	for (int i = 1; i <= n; i++) dis[i] = -100000;
	dis[1] = 0;
	for (int i = 1; i <= n; i ++){
		flag = 0;
		for (int j = 1; j <= tot; j++){
			if (dis[c[j].tt] < dis[c[j].ff] + c[j].ww){
				dis[c[j].tt] = dis[c[j].ff] + c[j].ww;
				flag = 1;
			}
		}
		if (!flag) {
			return 1;
		}
	}
	if (flag){
		for (int i = 1; i <= n; i ++){
			if (dis[c[i].tt] < dis[c[i].ff] + c[i].ww){
				return 0;
			}
		}
	}
	return 1;
}
 
void print(){
	int temp = 0x3f3f3f3f;
	for (int i = 1; i <= n; i ++) temp = min(temp,dis[i]);
	for(int i = 1; i <= n; i++) printf("%d\n", abs(temp - dis[i]));
	return;
}
 
int main(){
	freopen("work.in","r",stdin);
	freopen("work.out","w",stdout);
	scanf("%d%d",&n,&m);
	int x,y,z;
	for (int i = 1; i <= m; i++){
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,-z);
	}
	if (bellman_ford()) print();
	else puts("NO SOLUTION");
	return 0;
}