TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

84.6% (99/117)

Submission's AC Ratio

20.1% (177/880)

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$。

Output Format

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

Sample Input 1

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

Sample Output 1

5

Hints

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

Problem Source

Problem Set by Yihda Yol

Subtasks

No. Testdata Range Constraints Score
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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2500 131072 262144 1 5
1 2500 131072 262144 2 5
2 2500 131072 262144 3 4 5
3 2500 131072 262144 4 5
4 2500 131072 262144 5