这天，tokitsukaze带着她的舰队去才归一儿海探索。这个海域有n个站点，深海舰队控制着这片海域的m条航线，这些航线连接着这n个点，第i条航线连接着ui，vi两个点。航线都是正确的，也就是说没有重复的航线，也没有任何一个点与自己相连。tokitsukaze的舰队经过第i条航线时，会受到来自深海舰队的ai点伤害。

tokitsukaze可以在某个休息站点将接下来的战斗切换至夜战模式，这样在她的舰队经过第i条航线时，受到的伤害就变为bi，不过一旦切换到夜战模式就不能再次切换回来，所以她必须考虑清楚在哪里切换。

现在有个限时活动。活动难度分为1,2,3,4,...n，在难度1下，tokitsukaze可以在任意站点切换到夜战模式，而在难度2下，不能在站点1切换到夜战模式，在难度3下，不能在站点1,2切换模式...以此类推，即在难度k下，tokitsukaze不能在站点1,2,3,4,5...k-1切换模式。同时，活动还要求在游戏结束时必须处于夜战模式。

现在tokitsukaze的舰队从s点出发，要前往深海大本营所在的t点。请你告诉她，在难度为1,2,3,4,5...n时，她的舰队结束游戏时受到的最小伤害。

第一行包括2个正整数n，m，(2≤n≤10^5，1≤m≤min(n*(n-1)/2,10^5))。
接下来m行，每行包括4个正整数u，v，a，b，(1≤u,v≤n，1≤a,b≤10^9)。
最后一行包括2个正整数s，t，(1≤s,t≤n)。

请你告诉tokitsukaze，在难度为1,2,3,4,5...n时，她的舰队处于夜战模式结束游戏受到的最小伤害。

4 3
1 4 1 30
1 2 1 10
1 3 20 1
2 3

2
11
21
33

活动难度为1时，在编号为1的点切换模式，受到的最小伤害为2。
活动难度为2时，在编号为2的点切换模式，受到的最小伤害为11。
活动难度为3时，在编号为3的点切换模式，受到的最小伤害为21。
活动难度为4时，在编号为4的点切换模式，受到的最小伤害为33。

4 3
1 4 30 1
1 2 10 1
1 3 20 1
3 1

1
1
1
51

活动难度为1时，在编号为3的点切换模式，受到的最小伤害为1。
活动难度为2时，在编号为3的点切换模式，受到的最小伤害为1。
活动难度为3时，在编号为3的点切换模式，受到的最小伤害为1。
活动难度为4时，在编号为4的点切换模式，受到的最小伤害为51。路线是3-1-4-1。因为必须处于夜战模式结束游戏，所以在到达1后还要拐去4去切换模式。