题目描述

瓜瓜已经厌倦了对他唯命是从的集训队，他打算外出征服其他地盘(一旦他到达了那个地盘，地盘就会被他的豪气征服)。在地图上共有 $n$ 个地盘（编号从 $1$ 到 $n$），地盘间一开始没有道路，但是瓜瓜可以发动他的独特技能“蓄意轰拳”，耗费 $w_i$ 的豪意值，迫使驻守 $[L_1, R_1]$ 到 $[L_2, R_2]$ 地盘的女守卫们打开永久单向传送门，使得处于第一块范围内的任一地盘，都能到达第二块范围内任一地盘。 瓜瓜开始在 $s$ 地盘，他最后希望到达 $t$ 地盘。 虽然瓜瓜拥有各种技能，但他并不是很擅长计算，你需要帮他算出征服 $t$ 地盘的最少豪意值，否则将会吃到他的“强手裂颅”！

输入格式

第一行有 4 个整数，给出地盘个数 $n(n \leqslant 10^4)$ ，可以发动“蓄意轰拳”的次数 $m(m \leqslant 10^3)$，起点 $s$，终点 $t$。

接下来 $m$ 行，给出 $L_1,R_1,L_2,R_2,w$ ，均为正整数。代表瓜瓜可以耗费 $w_i(1 \leqslant w \leqslant 10^5)$ 的豪意值，使得 $[L_1, R_1]$ 到 $[L_2, R_2]$ 的女守卫们打开传送门。

保证 $1 \leqslant L_1 \leqslant R_1, L_2 \leqslant R_2 \leqslant n$ ，答案不超过 $10^9$。

输出格式

输出征服 $t$

的最少豪意值。如果无法征服 $t$，输出 $-1$。

样例

5 3 1 5
1 2 3 4 5
1 1 2 3 4
2 3 5 5 3

7