def g;gets.split.map &:to_i;end
while(c,n,m,s,d=g)[0]>0
l=(0..n).map{{}}
m.times{a,b,f=g;l[a][b]=l[b][a]=f}
q=[[0,s]+[0]*c]
until(o,i,*a=q.sort!.shift;i==d)
l.map{|h|h.delete i}
l[i].map{|k,v|t,*u=(a+[v]).sort;q<<[o+v/2+t/2,k]+u}
end
p o
end