在帶權(quán)有向圖G中，給定一個源點v，求從v到G中的其余各頂點的最短路徑問題，叫做單源點的最短路徑問題。

在常用的單源點最短路徑算法中，迪杰斯特拉算法是最為常用的一種，是一種按照路徑長度遞增的次序產(chǎn)生最短路徑的算法。

可將迪杰斯特拉算法描述如下：

在本題中，讀入一個有向圖的帶權(quán)鄰接矩陣（即數(shù)組表示），建立有向圖并按照以上描述中的算法求出源點至每一個其它頂點的最短路徑長度。

輸入的第一行包含2個正整數(shù)n和s，表示圖中共有n個頂點，且源點為s。其中n不超過50，s小于n。

以后的n行中每行有n個用空格隔開的整數(shù)。對于第i行的第j個整數(shù)，如果大于0，則表示第i個頂點有指向第j個頂點的有向邊，且權(quán)值為對應(yīng)的整數(shù)值；如果這個整數(shù)為0，則表示沒有i指向j的有向邊。當(dāng)i和j相等的時候，保證對應(yīng)的整數(shù)為0。

只有一行，共有n-1個整數(shù)，表示源點至其它每一個頂點的最短路徑長度。如果不存在從源點至相應(yīng)頂點的路徑，輸出-1。

請注意行尾輸出換行。