该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

n座城市构成了一个城市网络，编号为0到n-1。其中分布着m条双向道路，每条道路连接两个城市，并且每条道路具有两个属性：距离d和通行费用c。你的目标是从起点城市S到终点城市T，请找出一条最优路径，使其同时满足以下两个条件： 1）该路径的总距离最短; 2）在所有总距离最短的路径中，该路径的通行费用最少。 请输出满足条件的路径的通行费用。如果从城市S到城市T之间不存在任何路径，则输出-1。

Format

Input

第一行包含四个整数n,m,S和T，分别表示城市的数量，道路的数量，以及起点城市和终点城市的编号; 接下来m行，每行包含四个整数u,v,d,c,表示有一条双向道路连接城市u和城市v，其距离为d，通行费用为c。

Output

一个整数，表示城市S到城市T的满足题目要求的路径的通行费用。如果不存在路径，则输出-1。

Samples

5 6 0 4
0 1 2 3
0 2 4 2
1 2 1 1
1 3 7 3
2 4 3 6
3 4 2 1

10

Limitation

测试点1~10： 1<=n<=10⁵; 1<=m<=2*10⁵; 1<=d,c<=10⁹; 0<=S,T<=n-1。