最小傳遞延遲

題目

通訊網(wǎng)絡(luò)中有N個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)
用1 ~ N進(jìn)行標(biāo)識(shí)
網(wǎng)絡(luò)通過(guò)一個(gè)有向無(wú)環(huán)圖進(jìn)行表示
其中圖的邊的值，表示節(jié)點(diǎn)之間的消息傳遞延遲
現(xiàn)給定相連節(jié)點(diǎn)之間的延時(shí)列表times[i]={u,v,w}
其中u表示源節(jié)點(diǎn)，v表示目的節(jié)點(diǎn)，w表示u和v之間的消息傳遞延時(shí)
請(qǐng)計(jì)算給定源節(jié)點(diǎn)到目的節(jié)點(diǎn)的最小傳遞延遲
如果目的節(jié)點(diǎn)不可達(dá)請(qǐng)返回-1
注意：N的取值范圍是1 ~ 100
延遲times列表長(zhǎng)度不超過(guò)6000
且1 <= u,v <= N,0 <= w <= 100

輸入

輸入第一行為兩個(gè)正整數(shù)，分別為網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)N以及延時(shí)列表長(zhǎng)度M，用空格分隔
接下來(lái)的M行為兩個(gè)節(jié)點(diǎn)間的延時(shí)列表[u,v,w]
輸入的最后一行為兩個(gè)正整數(shù)u和v分別表示源節(jié)點(diǎn)和目的節(jié)點(diǎn)

輸出

輸出一個(gè)整數(shù)表示源節(jié)點(diǎn)到目的節(jié)點(diǎn)的最小延時(shí)

示例一

輸入

3 3
1 2 11
2 3 13
1