#P18577. Transfers in a Cactus Graph

Transfers in a Cactus Graph

Transfers in a Cactus Graph

某个交通网络中的每个顶点都是一个换乘枢纽。当你位于顶点 uu 时,可以购买一张前往任意另一个顶点 vv 的车票。这张车票的价格为

bu+pu⋅dist⁡(u,v),b_u+p_u\cdot\operatorname{dist}(u,v),

其中 dist⁡(u,v)\operatorname{dist}(u,v) 是网络原图中 uu 与 vv 之间的最短路长度。抵达 vv 后,你可以立即结束旅程,也可以从 vv 购买下一张车票。换乘次数没有限制。整个旅程的费用是所有已购车票的价格之和。

交通网络是一个连通、无向、带权的仙人掌图,即每条边至多属于一个简单环。图有 nn 个顶点、mm 条边,第 jj 条边的长度为 wjw_j。每个顶点 ii 的参数为 bi,pib_i,p_i。

请对每个顶点 vv,求出从顶点 11 到顶点 vv 的旅程的最小费用。

输入格式

第一行一个整数 tt,表示测试用例数,1≤t≤5001\le t\le500。

每个测试用例的第一行包含两个整数 n,mn,m,满足 2≤n≤1052\le n\le10^5,n−1≤m≤⌊3(n−1)/2⌋n-1\le m\le\lfloor3(n-1)/2\rfloor。

接下来 mm 行描述边。每行三个整数 u,v,wu,v,w,表示一条连接 uu 和 vv、长度为 ww 的双向边,1≤u,v≤n1\le u,v\le n,1≤w≤1041\le w\le10^4。

保证图连通、是仙人掌图,且无自环、无重边。

接下来 nn 行,第 ii 行包含两个整数 bi,pib_i,p_i,其中 0≤bi≤1090\le b_i\le10^9,1≤pi≤1041\le p_i\le10^4。

所有测试用例的 nn 之和不超过 10510^5,mm 之和不超过 2⋅1052\cdot10^5。

输出格式

对每个测试用例输出一行 nn 个整数,第 vv 个整数是从顶点 11 到顶点 vv 的最小旅程费用。顶点 11 的答案为 00。

原样例

2
3 2
1 2 5
2 3 4
10 1
20 2
30 5
3 2
1 2 5
2 3 5
0 10
1 1
100 10
0 15 19
0 50 56