记录编号	23767	评测结果	AWWWWWWWW
题目名称	工程规划	最终得分	11
用户昵称	ybh	是否通过	未通过
代码语言	Pascal	运行时间	0.012 s
提交时间	2011-03-19 12:16:49	内存使用	0.24 MiB

{工程规划
 差分约束系统 最短路径
 Author: yangbohua
 Time: 2011-03-19}

program work;
var
  list,q,dist:array[0..1005] of longint;
  v,w,next:array[0..6005] of longint;
  b:array[0..1005] of boolean;
  n,i,j,h,t,u,num,m,r1,r2,r3,min,fu:longint;
begin
  assign(input,'work.in');
  reset(input);
  assign(output,'work.out');
  rewrite(output);

  readln(n,m);
  fillchar(list,sizeof(list),0);
  fillchar(next,sizeof(next),0);
  fillchar(w,sizeof(w),0);
  num:=0;
  fu:=0;
  for i:=1 to m do
  begin
    readln(r2,r1,r3);
    inc(num);
    v[num]:=r2;
    w[num]:=r3;
    next[num]:=list[r1];
    list[r1]:=num;
    if r3<0 then fu:=fu+r3;
  end;
  for i:=1 to n do
  begin
    inc(num);
    v[num]:=i;
    w[num]:=0;
    next[num]:=list[0];
    list[0]:=num;
  end;

  fillchar(q,sizeof(q),0);
  fillchar(b,sizeof(b),false);
  for i:=1 to n do
    dist[i]:=maxlongint;
  dist[0]:=0;
  h:=0;
  t:=1;
  q[1]:=0;
  b[0]:=true;
  while h<>t do
  begin
    h:=(h+1) mod (n+1);
    i:=q[h];
    u:=list[i];
    while u>0 do
    begin
      j:=v[u];
      if dist[i]+w[u]<dist[j] then
      begin
        dist[j]:=dist[i]+w[u];
        if b[j]=false then
        begin
          t:=(t+1) mod (n+1);
          q[t]:=j;
          b[j]:=true;
        end;
        if dist[j]<fu then
        begin
          writeln('NO SOLUTION');
          close(input);
          close(output);
          halt
        end;
      end;
      u:=next[u];
    end;
    b[i]:=false;
  end;

  min:=0;
  for i:=1 to n do
    if dist[i]<min then min:=dist[i];
  for i:=1 to n do
    writeln(dist[i]-min);

  close(input);
  close(output)
end.