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

/*
	author  :hzoi_天翔 
	title   :工程规划
	ALG     :差分约束 Bellman-Ford 
	comment : 
*/

#include <cstdio>

#define  maxn  1002
#define  maxm  5002
#define  info  1000000

/*struct Star{
	int to , len , next ;
} map[maxm] ; int head[maxn] = {0} , tot = 0 ;

void addEdge(int to , int from , int len) {
	tot ++ ; map[tot].to = to ; map[tot].len = len ;
	map[tot].next = head[from] ; head[from] = tot ;
}*/

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

int n , m ;
int a , b , c , flag ;
int dis[maxn] = {0} ;
int cnt[maxn] = {0} ;//统计入队次数
bool inq[maxn] = {false} ;

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

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

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 ) ;
		//addEdge(a , b , c) ;
		edges[++tot](a,b,c) ;
	}
	if (Bellman_Ford()) printf("NO SOLUTION\n") ;
	else PrintfAns() ;
	return 0 ;
}