问题描述

A国有 $n$ 个城市，修建了 $m$ 条道路（道路双向都可以走），每条道路的长度为 $d$ ，走该路线要花费 $p$ 元的过路费。 请问：如果要从编号为 $s$ 的城市到编号为 $t$ 的城市，最短距离是多少，如果按最短距离来走要花多少钱？ 注意：如果有多条最短路，请输出花费最少的距离及花费。

输入格式

读入若干组数据，对于每组数据： 先输入 $n,m$ ，城市的编号是 $1 \sim n$，然后是 $m$ 行，每行 $4$ 个数 $a,b,d,p$ ，表示 $a$ 城市和 $b$ 城市之间有一条边，且其长度为 $d$ ，过路费花费为 $p$ 。 最后一行是两个数 $s,t$ ，表示起点编号为 $s$ ，终点编号为 $t$ 。 当读入 $n$ 和 $m$为 $0$ 时，表示输入结束。 ( $1 \lt n \le 1000, 0 \lt m \lt 100000$， $s \neq t$ )

输出格式

对于每组输入，输出一行有两个数， 表示最短距离及其花费。

样例

输入

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

输出

9 11