Jimmy最近覺得工作壓力很大。為了放鬆心情，他喜歡走路回家。 他的辦公室在森林的一邊，而他的家在森林的另一邊。當他在森林中散步時，看看小鳥、松鼠讓他覺得很快樂。
森林是那麼的美，Jimmy想要每天都走不同的路徑回家。但是他也不想要回家太晚，所以他總是選擇一條可以朝他家「前進」的路徑來走。所謂「前進」指的是他會選擇從A點走到B點如果B點存在一條到他家的路徑長度比A點到他家任一路徑的長度都來的短的話。請你算出Jimmy共有多少種不同的路徑可以走。
輸入包含多組測試資料。
每組測試資料的第1列包含2個整數 N （ 1 < N <= 1000）和 M，N代表共有多少個點（編號從1到 N，請注意：編號 1 的點為 Jimmy 的辦公室，編號 2 的點為 Jimmy 的家），M代表共有多少個連接2個點的邊。接下來的M列每列有3個整數 a, b, d。a,b為點的編號，d 為連接 a,b 的路徑長（在這裡 a,b 不會相同，1 <= d <= 1000000）。路徑是雙向的，且任2點之間僅有一條路徑連接。
輸入的最後一列僅有一個 0，請參考Sample Input。
5 6 1 3 2 1 4 2 3 4 3 1 5 12 4 2 34 5 2 24 7 8 1 3 1 1 4 1 3 7 1 7 4 1 7 5 1 6 7 1 5 2 1 6 2 1 5 7 1 3 2 1 4 2 3 4 3 1 5 12 4 2 34 5 2 25 4 5 1000 2 1 1 2 999 0
2 4 3 1
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||