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的最小花费。
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
HINT
QAQ在城市1变装成A种族的人（花费0），经过道路1—2（花费1），在城市2变装成B种族（花费3），经过道路2—4（花费2），在城市4不需要变装（花费0），经过道路4—5（花费1），到达目的地。此种选择总花费最低，为7。