记录编号	502581	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	月考统计	最终得分	100
用户昵称	6666	是否通过	通过
代码语言	C++	运行时间	0.506 s
提交时间	2018-07-27 14:24:04	内存使用	0.34 MiB

//
//  exam.cpp
//  
//
//  Created by apple on 2018/7/27.
//

#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
const int maxn=1005;
int n,m,ans[maxn];vector<int>son[maxn],v[maxn];
void Set(int prt,int to,int d){
    son[prt].push_back(to),v[prt].push_back(d);
}
void Max(int &x,int y){if(x<y)x=y;}
int dis[maxn],cnt[maxn];bool bein[maxn];queue<int>q;
bool Run(int S){
    memset(dis,0x3f,sizeof(dis));dis[S]=0;
    memset(cnt,0,sizeof(cnt));
    q.push(S),bein[S]=true;
    while(!q.empty()){
        int rt=q.front();q.pop(),bein[rt]=false;
        for(int i=0;i<son[rt].size();i++){
            int to=son[rt][i];
            if(dis[to]>dis[rt]+v[rt][i]){
                dis[to]=dis[rt]+v[rt][i];
                cnt[to]=cnt[rt]+1;
                if(cnt[to]>n){
                    while(!q.empty())bein[q.front()]=false,q.pop();
                    return false;
                }
                if(!bein[to])bein[to]=true,q.push(to);
            }
        }
    }
    for(int i=1;i<=n;i++)Max(ans[S],max(0,-dis[i]));
    return true;
}
int main(){
    freopen("ExamStat.in","r",stdin);
    freopen("ExamStat.out","w",stdout);
    scanf("%d%d",&n,&m);int i,x,y,z;bool ff=false;
    while(m--)//ax-ay<=z//ax<=ay+z//ai-at>=?
        scanf("%d%d%d",&x,&y,&z),Set(y,x,z);
    for(i=1;i<=n;i++)if(!Run(i)){printf("SOMEONE LAY!\n");return 0;}
    for(i=1;i<=n;i++)printf("%d ",ans[i]);
}