题目描述

圣地亚哥境内有\(n\)个农场，编号为\(1 \sim n\)。两个农场之间可能有路直接相连，共计\(m\)条路。编号为\(A\)的农场有一个大型仓库，堆放着数千袋金坷垃。编号为\(B\)的农场由于长期干旱和水土流失，急需不流失、不蒸发的高效肥料。
农业局决定派遣一队运输车从农场\(A\)给农场\(B\)运送金坷垃。由于形式严峻，必须在\(T\)分钟之内送达。运输队的队长十分熟悉农场之间的路况，他知道每条路需要多长时间走完，途中会耗费多少柴油。由于油钱需要运输队的人自己掏腰包，所以队长不想在路上耗费太多的柴油。
请你计算，在按时送达的前提下，运输队至少需要耗费多少柴油。

格式

输入格式

第一行是两个正整数\(n,m\)；
之后每行4个正整数\(x,y,d,c\)，表示农场\(x\)和\(y\)之间有一条道路直接相连，走这条道路耗时为\(d\)分钟，消耗柴油的量为\(c\)。输入保证无重边和自环；
之后一行是两个正整数\(A,B\)，保证\(1 \le A,B \le n\)且\(A \ne B\)；
最后一行是一个正整数\(T\)。

输出格式

一个正数，如果能按时送达，输出最少耗费柴油的量；如果不能，输出-1。

样例

输入

4 5
1 2 2 3
1 3 3 5
1 4 7 10
2 4 4 6
3 4 2 6
1 4
5

输出

11

数据规模及限制

时间限制1s，空间限制128MB
共10组测试数据。所有数据都满足：
\(n \le 100, \phantom{x} m \le 1000, \phantom{x} 1 \le d \le 10^4, \phantom{x} T \le 10^7, \phantom{x} 1 \le c \le 10^6\)。

来源

2017.7 太原五中高一集训
Vijos主站“丛林探险”的数据加强版
原题链接：https://vijos.org/p/1082