记录编号	14707	评测结果	AAAAAAAAAA
题目名称	[USACO Oct09] 热浪	最终得分	100
用户昵称	ReimBurSe.	是否通过	通过
代码语言	Pascal	运行时间	0.509 s
提交时间	2009-11-03 15:23:05	内存使用	47.82 MiB

Program heatwvx;
 
Type
sc=array [1..2500,0..2500] of longint;
sc1=array [1..2500] of boolean;
 
Var
a,s:sc;
panduan:sc1;
i,j:longint;
n,m,q,z:longint;
x,y,k:longint;
min,p:longint;
 
Begin
assign(input,'heatwvx.in');
assign(output,'heatwvx.out');
reset(input);
rewrite(output);
readln(n,m,q,z);
for i:=1 to n do
 for j:=0 to n do
  a[i,j]:=99999999;
for j:=1 to m do begin
 readln(x,y,k);
 s[x,0]:=s[x,0]+1;
 s[y,0]:=s[y,0]+1;
 s[x,y]:=k;
 s[y,x]:=k;
end;
for i:=1 to n do panduan[i]:=true;
panduan[q]:=false;
for i:=1 to n do begin
 if s[q,i]<>0 then a[1,i]:=s[q,i]
 else a[1,i]:=99999999;
end;
for i:=2 to n do begin
 min:=99999999;
 for j:=1 to n do begin
  if (panduan[j]=true)and(a[i-1,j]<min) then begin
   min:=a[i-1,j];
   p:=j;
  end;
 end;
 for j:=1 to n do begin
  a[i,j]:=a[i-1,j];
  if s[p,j]<>0 then
   if s[p,j]+a[i-1,p]<a[i-1,j] then
    a[i,j]:=s[p,j]+a[i-1,p];
  end;
 panduan[p]:=false;
end;
writeln(a[n,z]);
close(input);
close(output);
End.