def g;gets.split.map &:to_i;end
while(m,_,o,d=g;m>0)
l=g
h=Hash.new{|i,k|i[k]={}}
d.times{
a,b,c=gets.split
h[a][b]=h[b][a]=c.to_i
}
q=[[?H,[],0]]
x=[]
e={}
while(a,b,c=q.sort_by!{|i|i[2]}.shift;a)
b.sort!
e[t=[a,b]]&&c>e[t]?(next):e[t]=c
a==?D&&(x<< c;b[m-1]&&break)
h[a].map{|k,v|b.index(k)||(q<<(k[0]==?C?[k,b+[k],c+v*o-l[k[1].to_i-1]]:[k,b,c+v*o]))}
end
p x.min
end