问题文

※"きたむー"是此问题的作者协助起草问题的人的名字。另外，"きたむー"的女朋友并不是"いろはちゃん"。

今天对于"きたむー"和他的女朋友来说是期待已久的"第一次一起摘花"纪念日。他本打算在今天送给她$K$束花。但是，由于他管理的纪念日太多，他忘记买花了。于是他决定在上学的路上买花。

"きたむー"所居住的城市有$N$个车站，每个车站都有从$1$到$N$的编号。此外，他所乘坐的铁路有$M$条线路，第$i$条线路连接车站$A_i$和$B_i$，票价为$C_i$日元，并且可以相互往返。在车站$j$，可以以$Y_j$日元的价格购买任意数量的花束，每束花中含有$X_j$朵花。他住在车站$1$附近，学校位于车站$N$附近。

现在，他需要购买至少$K$束花后才能上学，那么交通费和花的总金额的最小值是多少呢？

约束条件

• 所有输入均为整数。
• $2 \leq N \leq 1000$
• $1 \leq M \leq 2000$
• $1 \leq K \leq 1000$
• $1 \leq A_i, B_i \leq N$ $(1 \leq i \leq M)$