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],[0,0,1e9]]
x=[]
e={}
while(a,b,c=q.shift;a)
e[t=[a,b]]&&e[t]<c&&next
e[t]=c
a==?D&&(x<< c;b[m-1]&&break)
h[a].each{|k,v|
b.index(k)||(
u=k[0]==?C?[k,(b+[k]).sort,c+v*o-l[k[1].to_i-1]]:[k,b,c+v*o]
q[(0...q.size).bsearch{|i|q[i][2]>u[2]},0]=[u]
)
}
end
p x.min
end