152. Day 4 PD. 重返榮耀

重返榮耀

題目敘述

運算之星「阿波銳特」中有四家運算器的工廠，分別是負責組裝的 ADD、零件分解的 SUB、模組設計的 MUL 以及回收業者 DIV 。原先 ADD 是阿波銳特裡面最大的工廠，但由於一例一休的影響，ADD 在過去十年間的業績一落千丈，隨時都有倒閉的危險。但最近有消息指出 ADD 運用量子重力以及大強力對撞機，找出了使零件自動組裝的機制，其他三家工廠無不聞之色變，因此他們找了你來想辦法阻止 ADD 重返榮耀。他們想出最好的方法就是阻礙 ADD 零件的運輸。

阿波銳特所在的宇宙是由好幾個星球所共同組成的，有一些星球之間有傳送門可以運輸資源，但是傳送門只能單向地傳輸。阿波銳特的零件都是由星球「破督社」製造，再透過一些傳送門輾轉地運送到阿波銳特。 SUB、MUL跟DIV 從傳送門的製造商那裡拿到了關閉傳送門的機器，能夠讓傳送門暫時無法工作，但關閉的時候需要的一些能量。他們的目標是讓破督社製造的零件無法運到阿波銳特，嚇一嚇 ADD。如果能量使用過多，可能會需要建設新的核電廠，但是他們又希望能建立非核家園，因此需要你告訴他們最少需要使用多少能量。

輸入說明

本題目有多筆測資。

第一行有一個正整數 $T$ 代表測資的數量。

每筆測資的第一行有四個整數 $N, M, x, y$ ，分別代表星球個數、傳送門個數、破督社的星球編號以及阿波銳特的星球編號。

接下來有 $M$ 行，每行有三個整數 $u, v, c$ ，表示有一道從 $u$ 到 $v$ 的傳送門，關閉這道傳送門需要 $c$ 單位的能量。

• $ 1 \leq T \leq 5 $
• $ 2 \leq N \leq 100 $, $ 0 \leq M \leq 1,000 $
• $ 1 \leq x,y \leq N $ 且 $ x \ne y$
• $ 1 \leq u,v \leq N $, $ 0 \leq c \leq 3,000,000 $

注意：兩個星球之間可能有多個傳送門。

輸出說明

對於每一筆測資，請輸出阻止 ADD 重返榮耀最少需要多少能量。格式參照範例輸出。

範例輸入

2
4 3 1 4
1 2 3
2 3 4
3 4 5
4 4 2 3
2 1 2
2 4 5
1 4 3
4 3 10

範例輸出

3
7

提示

N/A

Judge Setting

run-time limit: 1000 ms
memory limit: 256000000 byte
測資數量: 0