#P17854. [Ontak2019]PIZ

[Ontak2019]PIZ

— 披萨外送博弈

一座城市有 nn 栋房屋和 mm 条双向道路,道路有正长度,任意两栋房屋互相可达,没有自环和重边。两兄弟分别在房屋 aa、bb 开披萨店,房屋 ii 能带来收益 pip_i,这个收益可以为负。

两人进行如下游戏,由第一位兄弟先手,之后轮流行动。每人的配送半径最初都是 −1-1,所有房屋最初都没有归属。

轮到某人时,他必须增大自己的配送半径。所有尚未归属任何人、且到他的店的最短路距离不超过新半径的房屋,都会永久归他所有。本次行动必须至少获得一栋此前没有归属的房屋;已经归对方的房屋不会被抢走。

所有房屋都有归属时游戏结束。每人的最终收益等于归他的房屋的 pip_i 之和。两人都希望最大化自己的最终收益。

求双方均采用最优策略时,各自的最终收益。两家店所在的房屋本身也参与争夺,其收益保证为0。

输入格式

第一行两个整数 n,mn,m。

第二行两个不同的整数 a,ba,b,表示先手和后手的店的位置。

第三行 nn 个整数 p1,…,pnp_1,\ldots,p_n。

接下来 mm 行,每行三个整数 ui,vi,ℓiu_i,v_i,\ell_i,表示道路的两个端点及长度。

输出格式

输出两个整数,依次表示先手和后手的最优最终收益。

数据范围

3≤n≤20003\le n\le2000,n−1≤m≤105n-1\le m\le10^5,1≤a,b≤n1\le a,b\le n,a≠ba\ne b。

−109≤pi≤109-10^9\le p_i\le10^9,pa=pb=0p_a=p_b=0;1≤ℓi≤1091\le\ell_i\le10^9。保证图连通、无自环及重边。

子任务 附加限制 分值
1 n,m≤20n,m\le20 20
2 n≤100,m≤1000n\le100,m\le1000 40
3 无

样例 1

输入:

4 3
1 2
0 0 1 -1
1 3 1
2 3 1
3 4 1

输出:

0 0