Problem G: QAQ的变装术

Problem G: QAQ的变装术

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

某个国家有n座城市,m条道路,某些城市之间通过这些道路相连接。这个城市有两个种族(A种族和B种族),不同种族的人经过不同道路需要花费不同的过路费。QAQ的家在城市S,他明天需要到城市E参加工作,但又不想在路上有过多的花费,所以他学会了变装术,他可以在任意的城市进行变装,次数不限,变装完后他就是属于另一个种族的人,不过变装需要另外花费C元。请你帮他规划一条线路使得到达目的地的总花费最低,并输出金额。
注意:QAQ在出发时可以随便选择变装成A种族或B种族,此时不需要额外花费。

Input

第一行包含五个数字,分别为城市数量n,道路数量m,出发点S,目的地E,变装的花费C
接下来m行,每行包括四个数字,分别为道路连接的城市X和城市Y,A、B种族经过所需的费用Acost和Bcost
1 <= n <= 100000
1 <= m <= 200000
1 <= C, Acost, Bcost <= 1000000000
保证图中没有重边和自环,S和E一定联通。

Output

输出一个数字,表示QAQ从城市S到城市E的最小花费。

Sample Input Copy

5 6 1 5 3
1 2 1 8
1 3 3 7
1 4 4 7
2 4 9 2
3 5 5 4
4 5 5 1

Sample Output Copy

7

HINT

QAQ在城市1变装成A种族的人(花费0),经过道路1—2(花费1),在城市2变装成B种族(花费3),经过道路2—4(花费2),在城市4不需要变装(花费0),经过道路4—5(花费1),到达目的地。此种选择总花费最低,为7。