50002. Final Prob. 2: 輸送帶

I'm a slow walker, but I never walk backwards.

拉基(Lucky)貓是仁仁(Jen-Jen)最好的動物朋友,他們最喜歡一起喵喵(meow, /miˈaʊ/)叫了。

今天,他們約好在上完DSA之後聚在一起喵喵叫。拉基貓上課的地方在社科院,而仁仁上課的地方在德田商旅。他們約在德田商旅地下室,所以拉基貓需要移動位置,但是仁仁不用。

因為社科院和德田商旅的距離實在是太遠了,為了極大化喵喵叫的時間以及節省體力,拉基貓想知道從社科院移動到德田商旅最少需要多少時間。

已知NTU的道路是由一條條連結各個系館的單向輸送帶(Conveyor Belt)構成的。每條輸送帶都有不同的速度,有些慢到可以在上面悠閒的翻CLRS,有些快到必須要注意隨時會撞上你的蝴蝶。

NTU發展出一個神奇的黑科技,讓任意兩條相交的輸送帶不會互相干擾。拉基貓是乖巧的好學生,所以不會在被輸送的途中,從一條輸送帶跳到另外一條輸送帶上。

有些系館之間可能兩個方向的輸送帶各有一條。在輸送量比較大的地方(像是小椰林道),也有可能有多條起點和終點一樣的輸送帶。

此外,為了避免造成某些系所的不滿,對於任意兩個系館X, Y,都存在路線可以從X輸送到Y。

你能幫拉基貓算出從社科院到德田商旅最少需要多少時間嗎?

Input

第一行是一個正整數$T$,代表接下來共有幾筆測資。

每筆測資的第一行是兩個正整數$N$及$M$,分別代表系館數和輸送帶數(系館從$0$編號到$N - 1$)。

下一行有兩個正整數$A$和$B$,分別代表社科院的編號和德田商旅的編號。

接下來有$M$行,每一行有三個正整數$u, v, w$,分別代表每條輸送帶的起點,終點,和從起點輸送到終點共需要花多少時間。

Output

對於每筆測資,輸出一行包含一個正整數,代表從社科院移動到德田商旅最少需要多少時間。

Subtasks

所有測資皆滿足: $T \leq 20$, $2 \leq N, M \leq 10^5$, $1 \leq w \leq 10^9$

  1. $w = 1$ (5 pts)
  2. 如果不重複經過同一系館,則從一棟系館到另一棟系館將只有唯一的走法 (5 pts)
  3. $N, M \leq 500$ (5 pts)
  4. $N, M \leq 5000$ (5 pts)
  5. 無額外限制 (5 pts)

Sample Input

1
3 6
0 1
0 1 2
1 0 3
0 2 7
2 1 6
2 1 7
1 2 8

Sample Output

2

Discussion