TopCoder

User's AC Ratio

87.5% (7/8)

Submission's AC Ratio

66.7% (14/21)

Tags

Description

從前從前,在「單行道國」中有兩個人,John和Jon。他們兩個人是死對頭,而且都住在同一個小鎮$A$。

「單行道國」顧名思義,這個國家每一條路都是連接兩個小鎮的單行道,並且國家中總共有$N$個小鎮,從$0$編號到$N-1$。這個國家的交通其實相當發達,所以對於任意兩個小鎮$X,Y$,都存在路線可以從$X$走到$Y$。另外,有些小鎮之間可能會兩個方向的單行道各有一條;甚至在重要的小鎮之間可能會有很多條起終點一樣的單行道。當然,單行道國的政府也看上了他們國家交通發達這件事情,於是決定在每一條道路都蓋一個收費站,任何一個開車經過的人民都要收過路費。

某一天,John要到$B$鎮去旅遊。沒想到,在他收拾好一切行李準備出發的時候,他卻聽說兩天前Jon剛好也去了$B$鎮一趟!身為Jon的死對頭,John決定說什麼也不要和Jon走類似的路線。幸好John知道Jon是個非常節省的人,所以Jon從$A$鎮到$B$鎮時一定會挑選總過路費最少的路線前往。

因此,John算出了Jon從$A$鎮到$B$鎮時繳了多少過路費,並且決定自己從$A$鎮前往$B$鎮的時候繳的總過路費一定要跟Jon不一樣。在滿足這個前提之下,John會讓自己繳的總過路費愈少愈好(當然,這樣有可能是必須要繞路的,也就是說John走的路線可能會重複經過某個小鎮或重複經過某一條單行道)。你能幫John算出他繳的總過路費和Jon繳的總過路費差了多少錢嗎?

Input Format

第一行有一個正整數$T$,代表總共有多少筆測資。

對於每筆測資,第一行有兩個正整數$N,M$,代表單行道國有$N$個小鎮和$M$條單行道;第二行有兩個非負整數$A,B$,分別代表John住的小鎮編號與他要去的小鎮編號。
接下來有$M$行,每一行有三個非負整數$A_i, B_i, K_i$,代表有一條小鎮$A_i$到小鎮$B_i$的單行道,且走這條路要繳$K_i$元的過路費。

對於所有測資,$1\leq T\leq 20; 2\leq N,M\leq 10^ 5;1\leq K_i\leq 10^ 9$。

子任務(測資) 額外限制 分數
1 (0) 每一條單行道的過路費都是1 20
2 (1) 如果不重複經過小鎮,則從一小鎮到另一小鎮將只有唯一的路線可以通行 20
3 (2) $N,M \leq 500$ 10
4 (2~3) $N,M \leq 5000$ 10
5 (0~4) 無限制 40

Output Format

對於每筆測資輸出一行包含一個整數,代表John繳的總過路費減掉Jon繳的總過路費

Sample Input

1
3 4
0 1
0 1 2
1 0 3
0 2 7
2 1 6

Sample Output

5

Hints

範例測資中,Jon會走0->1,總共花2元;John會走0->1->0->1,總共花7元。(0->2->1要花13元,並不是最佳的走法。)

Problem Source

Problem Set by Yihda Yol

Subtasks

For Testdata: 0 ~ 0, Score: 20
For Testdata: 1 ~ 1, Score: 20
For Testdata: 2 ~ 2, Score: 10
For Testdata: 2 ~ 3, Score: 10
For Testdata: 0 ~ 4, Score: 40
No. Time Limit (ms) Memory Limit (KiB)
0 2500 131072
1 2500 131072
2 2500 131072
3 2500 131072
4 2500 131072