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}
e=(0..n).map{[]}
q=[[0,s,0]]
p loop{o,c,t=q.shift
e[c][t]&&next
c==d&&(break o)
e[c][t]=1
l[c].map{|k,v|q<<[o+v,k,t];t<2&&q<<[o+v/2,k,t+1]}
q.sort!
}
end