住在烏龜國的兔子又想和烏龜比賽跑步了！烏龜國的地圖可以看成一張 $N$ 點 $M$ 邊的有向圖，第 $i$ 條邊是從點 $u_i$ 到點 $v_i$，需要花費 $w_i$ 分鐘（烏龜跟兔子跑得一樣快）。

然而烏龜決定想要蹺掉這次的比賽。他的計畫如下：

烏龜會在比賽前告訴兔子一條從起點到終點的最短路徑 $P$。兔子在路徑 $P$ 上的每一條邊都安裝了監視器以監視有沒有選手通過那條邊。
身為嗨客，烏龜能夠駭進一些監視器，並讓那些監視器的紀錄變成烏龜爬的影像。
在比賽結束後，他會再告訴兔子一條最短路徑 $Q$，使得路徑 $Q$ 上所有之前安裝的監視器都被他駭入了。這樣他就可以宣稱自己也走了最短路徑抵達終點，讓兔子沒辦法找到烏龜沒出門的證據。

他們已經決定好比賽的起點是點 $1$，而終點還沒有決定，可能是點 $1$ 到點 $N$ 中的任何一個。對於每個可能的終點，請你幫忙烏龜計算他最少需要駭進幾個監視器。

註1：最短路徑是總花費時間最少的路徑。
註2：烏龜和兔子不是同時比賽，所以兔子不會發現烏龜其實沒抵達終點。
註3：兔子可以接受烏龜反悔，在比賽之後說他走的不是原本定製的那條路。