卡碼網：94. 城市間貨物運輸 I

94. 城市間貨物運輸 I

題目描述

某國為促進城市間經濟交流，決定對貨物運輸提供補貼。共有 n 個編號為 1 到 n 的城市，通過道路網絡連接，網絡中的道路僅允許從某個城市單向通行到另一個城市，不能反向通行。

網絡中的道路都有各自的運輸成本和政府補貼，道路的權值計算方式為：運輸成本 - 政府補貼。權值為正表示扣除了政府補貼后運輸貨物仍需支付的費用；權值為負則表示政府的補貼超過了支出的運輸成本，實際表現為運輸過程中還能賺取一定的收益。

請找出從城市 1 到城市 n 的所有可能路徑中，綜合政府補貼后的最低運輸成本。如果最低運輸成本是一個負數，它表示在遵循最優路徑的情況下，運輸過程中反而能夠實現盈利。

城市 1 到城市 n 之間可能會出現沒有路徑的情況，同時保證道路網絡中不存在任何負權回路。

輸入描述

第一行包含兩個正整數，第一個正整數 n 表示該國一共有 n 個城市，第二個整數 m 表示這些城市中共有 m 條道路。 

接下來為 m 行，每行包括三個整數，s、t 和 v，表示 s 號城市運輸貨物到達 t 號城市，道路權值為 v （單向圖）。

輸出描述

如果能夠從城市 1 到連通到城市 n， 請輸出一個整數，表示運輸成本。如果該整數是負數，則表示實現了盈利。如果從城市 1 沒有路徑可達城市 n，請輸出 "unconnected"。

輸入示例

6 7
5 6 -2
1 2 1
5 3 1
2 5 2
2 4 -3
4 6 4
1 3 5

輸出示例

1

提示信息

示例中最佳路徑是從 1 -> 2 -> 5 -> 6，路上的權值分別為 1 2 -2，最終的最低運輸成本為 1 + 2 + (-2) = 1。

示例 2：

4 2
1 2 -1
3 4 -1

在此示例中，無法找到一條路徑從 1 通往 4，所以