题目描述

圣地亚哥境内有$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