最小傳遞延遲

題目

通訊網(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í)

示例一

輸入