记录编号	121801	评测结果	AAAAAAAAA
题目名称	工程规划	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2014-09-21 15:30:50	内存使用	0.00 MiB

/*
	author  :hzoi_天翔 
	title   :工程规划 
	ALG     :差分约束 Bellman-Ford 求最长路 
	comment :不懂为什么求最长路才能过 ... 
*/

#include <cstdio>

#define  maxn  1002
#define  maxm  5002
#define  info  100000

struct Edge{
	int from , to , len ;
	bool operator () (int FROM,int TO,int LEN){
		this->from=FROM;this->to=TO;this->len=LEN;
	}
} edges[maxm] ; int tot = 0 ;

int n , m ;
int a , b , c ;
int dis[maxn] = {0} ;

bool Relax(int f, int t, int w) {
	if (dis[t] < dis[f]+w) dis[t] = dis[f]+w ;
	else return false ;
	return true ;
}

bool Bellman_Ford(){
	int i , j ;
	for (i = 1 ; i <= n ; i ++ ) dis[i] = -info ;
	dis[1] = 0 ;
	bool flag ;
	for (i = 1 ; i <= n ; i ++ ) {
		flag = false ; // 优化
		for (j = 1 ; j <= tot ; j ++ )
			if(Relax(edges[j].from , edges[j].to , edges[j].len))
				flag = true ;
		if( !flag ) break ;
	}
	for (j = 1 ; j <= tot ; j ++ )
		if (Relax(edges[i].from , edges[i].to , edges[i].len))
			return false ; // 有负圈
	return true ;
}

void PrintfAns(){
	int tmp = info ;
	for (int i = 1 ; i <= n ; i ++ ) if (dis[i] < tmp) tmp = dis[i] ;
	for (int i = 1 ; i <= n ; i ++ ) printf("%d\n", dis[i]-tmp ) ;
}

int main() {
	#define  READ
	#ifdef   READ
		freopen("work.in" ,"r",stdin ) ;
		freopen("work.out","w",stdout) ;
	#endif
	scanf ("%d%d", &n , &m ) ;
	for (int i = 1 ; i <= m ; i ++ ) {
		scanf("%d%d%d", &a , &b , &c ) ;
		edges[++tot](a,b,-c) ;
	}
	if (Bellman_Ford()) PrintfAns() ;
	else printf("NO SOLUTION\n") ;
	return 0 ;
}