T368063 一个一个一个拥堵的旅程

DC是一个大旅行家，他喜欢旅行并品尝各地美味的食物 ~~迫真~~ ，今天他和朋友WXY一起前往下北泽一家十分甚至九分著名的会员制餐厅就餐 ~~(:大嘘~~ ，因为为了这场旅行他们花了很多金金金金金钱钱钱钱钱，所以他们希望速达哟。 但很不幸有一些道路可能发生了黑色高级轿车被追尾事件导致道路拥堵，于是他们找到了你——希望你帮他们计算他们所花费时间的最小期望 ##### ~~Tips：因为作者也很菜，所以就把问题交给了屏幕前的各位dalao~~ ##### 暂无数据（因为没标程QWQ）

下北泽可看做是一个由$N$个点和$M$条无向边组成的连通图（不保证无重边），DC和WXY需要从$S$号点前往$T$号点，已知每条道路的原本通行时间为$T1_i$,他们问ChatGPT得知每条道路有$P_i$的概率发生拥堵导致通行时间增加$T2_i$。 但一位神秘的人士告诉他们下北泽今天只会有最多$K$条道路可能发生拥堵（即有$K$条道路的拥堵概率如ChatGPT所，请找出一条路径，使得他们所花费时间的期望最小

共$M+2$行； 第一行，三个正整数$N$,$M$,$K$分别表示点数，边数和最大可能发生拥堵道路的数量； 接下来$M$行，第$i-1$行有五个数$u_i$,$v_i$,$T1_i$,$T2_i$,$P_i$,表示从$u_i$到$v_i$有一条通过时间为$T1_i$的路，它有$P_i$的概率发生拥堵并增加$T2_i$的通过时间； 第$M+2$行，两个正整数$ST$,$ED$,分别表示起点与终点

共一行，花费时间的最小期望值（保留三位小数）

$1\le N \le 10^3$,$1\le M \le 5\times 10^3$,$1\le T1_i,T2_i \le 2\times 10^4$,$P_i$是一位小数，$0.1\le P_i \le 0.9$ 对于$5\%$的数据， $K=0$ 对于$15\%$的数据，$0\le K\le 1$ 对于$40\%$的数据，$0\le K \le14 $ 对于$65\%$的数据，$0\le K\le 114$ 对于$100 \%$的数据, $0\le K\le 514$