说明

$A$国有$n$个城市，修建了$m$条道路（道路双向都可以走），每条道路的长度为$d$，走该路线要花费$p$元的过路费。

请问：如果要从编号为$s$的城市到编号为$t$的城市，最短距离是多少，如果按最短距离来走要花多少钱？

注意：如果有多条最短路，请输出花费最少的距离及花费。

输入格式

读入若干组数据，对于每组数据：

先输入$n,m$，城市的编号是1~$n$，然后是$m$行，每行4个数$a,b,d,p$，表示$a$城市和$b$城市之间有一条边，且其长度为$d$，过路费花费为$p$

最后一行是两个数 $s,t$，表示起点编号为$s$，终点编号为$t$

当读入n和m为0时，表示输入结束。 $(1<n≤1000, 0<m<100000, s != t)$

输出格式

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

样例

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

9 11