最低热量

题目描述

小明将学校中的所有地点编号为$1$到$n$，其中起点被编号为$S$，终点被编号为$T$。

学校中有$m$条连接两个点的双向道路，保证从任意一个点可以通过道路到达学校中的所有点。每条路都有一个温度$t$，及通过一条路所需的时间$c$，在温度为$t$的路径跑单位时间，就会使她的热量增加$t$。

在经过的所有道路中最高温度最低的前提下，使小明到达终点时的热量最低（从起点出发时，小明的热量为$0$），输出此时小明经过路径的最高温度和小明到达终点时的热量。

输入格式

第一行由一个空格隔开的两个正整数$n$，$m$。

接下来$m$行，每行为四个整数$a$，$b$，$t$，$c$，分别代表双向道路的两个端点，温度和通过所需时间。

最后一行由一个空格隔开的两个正整数$S$，$T$。

输出格式

仅一行，为两个整数，分别代表最高温度和热量。

数据范围与提示

• 对于$10\%$的数据，$t = 0$；
• 另有$10\%$的数据，$c = 0$；
• 另有$30\%$的数据，$n < 2000$；
• 对于$100\%$的数据，$1 \leq n \leq 5 \times 10^{5}$，$1 \leq m \leq 10^{6}$，$0 \leq t \leq 10^{4}$，$0 \leq c \leq 10^{8}$，$1 \leq a,b,S,T \leq n$，且$S \neq T$。

样例

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

3 24