"路過了學校花店 荒野到海邊 有一種浪漫的愛是浪費時間。" (林宥嘉‧兜圈)
黑章在經過反覆的愛情轉移過後，終於在背完該死的國文默寫後發現自己根本就沒有女朋友，也沒有妹妹。

這些年來的情調轉移究竟有什麼意義，不過是將情感寄託在左右手並來回轉移。但是在浪費了大量時間走過學校花店、荒野到海邊後，黑章得到了一項技能－－計算最短路徑。

於是他利用了這項技能走上了犯罪之路（別問我為什麼計算最短路徑可以犯罪，去問黑章），正當黑章打響了他在NECH的名號之後，警察卻找上了門來。他在千鈞一髮之際，逃向了NECH複雜的道路系統。雖然說黑章有可以計算最短路徑的特殊能力，但在NECH的道路上，距離是十分曖昧的觀念，黑章只知道，經過每條路會造成san值的浮動，於是，他將每一條道路都定義了一個san值距離(例：如果經過san值距離為3的道路會造成san值-3)

這個系統裡共有ｎ個城市，編號1 ~ n，而這些城市由m+k條有向的道路連接著。在這樣的情況下，要找出兩個城市之間的最短路徑對黑章來說根本就算不上是問題，但是你要知道，NECH的警察是會魔法的，他們可以對其中k條道路施展魔法，而這些魔法可以在黑章走過被施展魔法的道路後將所有被施展魔法的k條道路全部反轉。黑章在得知了這個消息後，嚇得大驚從早到晚失色(san值歸零？)，也因此失去了計算最短路的能力。

現在你已經知道了道路系統的狀況，請幫黑章計算兩城市間的最短路徑吧！