记录编号	137684	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	月考统计	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.646 s
提交时间	2014-11-05 02:31:04	内存使用	0.32 MiB

/*=============================================================================================================================*/
/*======================================================Code by Asm.Def========================================================*/
/*=============================================================================================================================*/
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <memory.h>
#include <vector>
#include <set>
#include <string>
#include <cstring>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <ctime>
#include <iterator>
#include <functional>
#include <cstdlib>
using namespace std;
/*===================================================================================*/
#define forall(it,v) for(__typeof(v.begin()) it = v.begin();it < v.end();++it) 
#define pb push_back
#define REP(i,j,k) for(i = j;i <= k;++i)
#define REPD(i,j,k) for(i = j;i >= k;--i)
#define iter(v) v::iterator
typedef long long LL;
template<typename T> void getint(T &x){
	char c = getchar();
	while(!isdigit(c))c = getchar();
	x = c - '0';
	while(isdigit(c = getchar()))x = x * 10 + c - '0';
}
/*============================================================================================*/
const int maxn = 2000 + 5;
int N, M;
struct edge{
	int to, w;
	edge(int T, int W):to(T), w(W){}
};
vector<edge> adj[maxn];

queue<int> Q;
bool inQ[maxn] = {0};
int dis[maxn] = {0}, cnt[maxn] = {0};
inline void init(){
	cin >> N >> M;
	int i, x, y, a;
	while(M--){
		cin >> x >> y >> a;
		adj[x].push_back(edge(y, -a));
	}
	for(i = 1;i <= N;++i)
		Q.push(i);inQ[i] = 1;cnt[i] = 1;
}
inline void work(){
	int i, t;
	iter(vector<edge>) it;
	while(!Q.empty()){
		t = Q.front();Q.pop();inQ[t] = 0;
		for(it = adj[t].begin();it != adj[t].end();++it)
			if(dis[t] + it->w > dis[it->to]){
				dis[it->to] = dis[t] + it->w;
				if(!inQ[it->to]){
					if(cnt[it->to] == N){
						cout << "SOMEONE LAY!" << endl;
						return;
					}
					Q.push(it->to);inQ[it->to] = 1;++cnt[it->to];
				}
			}
	}
	for(i = 1;i <= N;++i)
		cout << dis[i] << ' ';
}

int main(){
	#ifdef DEBUG
	freopen("test", "r", stdin);
	#else
	freopen("ExamStat.in", "r", stdin);
	freopen("ExamStat.out", "w", stdout);
	#endif
	
	init();
	work();
	
	#ifdef DEBUG
	//cout << endl << (double)clock() / CLOCKS_PER_SEC <<endl;
	#endif
	return 0;
}