與雪乃有約
發布時間: Feb. 8, 2021, 12:10 a.m. 最後更新時間: Sept. 15, 2023, 1:02 p.m. 時間限制: 1000ms 記憶體限制: 128M
在疫情還沒席捲日本時，社長和雪乃去了千葉迪士尼玩，至於遊玩的細節怕甜死別人我們先不討論。今天要說的是他們碰面時發生的事
他們約在編號$N$的舞浜車站，但由於你知道的，日本尤其是關東的鐵路網非常發達，去舞浜的路不止一條，於是他們要如何前往舞浜就變成一個很好的問題
假設他們一開始在編號$1$的千葉車站，而有$m$段鐵路連接兩個車站，第$i$段鐵路連接編號$u$的車站和編號$v$的車站，運行時間為$t$，且轉乘不耗費時間。由於社長和雪乃想盡早開始盡情享受在迪士尼裡的時光，所以他們希望搭車的時間越短越好，想請問你最少需要搭多久的車才能抵達舞浜，保證至少有一條路到得了舞浜
第一行有兩個正整數$N, m(1\leq N\leq 10^3, 1\leq m\leq \frac{N\times (N - 1)}{2})$，表示有$N$個車站及$m$段鐵路，接下來有$m$行輸入
接下來每行有三個正整數$u, v, t(1\leq u, v, \leq N, 1\leq t\leq 2\times 10^2)$
輸出一行一個整數表示最短時間，由於單位是以秒計算且數字可能很大，請輸出答案模$10^9+7$的值
複製範例
5 10 1 3 10 1 2 5 3 4 13 4 5 1 2 5 4 3 5 4 2 3 12 1 5 13 1 4 17 2 4 1
7
