def g;gets.split.map &:to_i;end
while(c,n,m,s,d=g)[0]>0
r=0..n
l=r.map{|i|r.map{[1e9,[0,0]]}}
m.times{a,b,f=g;l[a][b]=l[b][a]=[f/2,[0,f]]}
r.map{|k|r.map{|i|r.map{|j|
a,b=l[i][k]
c,t=l[k][j]
e,f,*h=(b+t).sort
l[i][j]=l[j][i]=[[a+c+(e+f)/2,h],l[i][j]].sort[0]
}}}
p l[s][d][0]
end