//
//  main.cpp
//  最短路径
//
//  Created by Yeah on 14-7-22.
//  Copyright (c) 2014年 Yeah. All rights reserved.
//

#include <iostream>
#include <deque>
#include <vector>
#include <string>
#include <sstream>
using namespace std;

const int MAXN = 5000;

const long long INF = 50000000000000;

struct Edge
{
    int To;
    long long Weight;
};

/**
 *    @brief  对输入的每一行进行处理，数据存入邻接矩阵
 *
 *    @param k      当前处理的顶点编号
 *    @param str    顶点编号对应的那一行输入数据
 *    @param Matrix 邻接矩阵，其中 Matrix[i][0] 可认为是一个指示器
 */
void Make_Matrix(int NodeNo, string str, long long Matrix[MAXN][MAXN])
{
    //string::size_type len = str.size();
    bool flag(false);
    long long tmp(0);
    for(string::iterator it(str.begin()); it != str.end(); ++it)
    {
        if ((*it == '-' && it == str.end() - 1) || (*it == '-' && *(it + 1) == ' '))
        {
            tmp = INF;
            continue;
        }
        
        if(isalnum(*it))
        {
            tmp = tmp * 10 + *it - '0';
        }
        else if(*it == '-' && isalnum(*(it + 1)))
            flag = 1;
        
        if(*it == ' ')
        {
            if(!flag)
                Matrix[NodeNo][++Matrix[NodeNo][0]] = tmp;
            if(flag)
                Matrix[NodeNo][++Matrix[NodeNo][0]] = tmp * -1;
            flag = false;
            tmp = 0;
        }
    }
}


/**
 *  @brief  SPFA 算法求源点到最短路径，处理结果保存在 Distance 数组里
 
 *  @param Source        源点编号（从 1 开始）
 *  @param NodeSum       图中顶点数
 *  @param in_Queue      数组，in_Queue[i] 标记编号为 i 的顶点是否在队列里面
 *  @param in_Cnt        数组，in_Cnt[i]   记录编号为 i 的顶点进入队列的总次数
 *  @param Distance      数组，Distance[i] 记录编号为 i 的顶点到源点的最短距离
 *  @param Adjacency_Map 数组，代表邻接表，vector::size() 为邻接顶点个数
 
 *  @return true  不存在负权环
 *  @return false 存在负权环
 
 *  @see http://www.nocow.cn/index.php/SPFA%E7%AE%97%E6%B3%95
 */

bool SPFA(int Source, int NodeSum, bool in_Queue[], int in_Cnt[], long long Distance[], vector<Edge> Adjacency_Map[])
{
    deque<int> DQ; // Double-ended Queue，双端队列，用于 SLF 优化策略
    
    // 初始化
    for (int i(1); i <= NodeSum; i++)
    {
        in_Queue[i] = false;
        in_Cnt[i]   = 0;
        Distance[i] = INF;
    }
    
    // 源点进队列
    DQ.push_back(Source);
    in_Queue[Source] = true;
    in_Cnt[Source]++;
    Distance[Source] = 0;
    
    while (!DQ.empty())
    {
        // 顶点出队列
        int Now       = DQ.front();
        in_Queue[Now] = false;
        DQ.pop_front();
        
        int To(0);
        for (int i(0); i < Adjacency_Map[Now].size(); i++)
        {
            To = Adjacency_Map[Now][i].To;
            if ((Distance[Now] < INF) && (Distance[To] > Distance[Now] + Adjacency_Map[Now][i].Weight))
            {
                // 松弛操作
                Distance[To] = Distance[Now] + Adjacency_Map[Now][i].Weight;
                
                if (!in_Queue[To])
                {
                    in_Queue[To] = true;
                    in_Cnt[To]++;
                    if (in_Cnt[To] == NodeSum)
                        return false; // 顶点入队总次数超过顶点个数，说明存在负权环
                    
                    if (!DQ.empty())
                    {
                        // 这里使用了 SLF (Small Label First) 策略来对算法进行优化
                        if(Distance[To] > Distance[DQ.front()])
                            DQ.push_back(To);
                        else
                            DQ.push_front(To);
                    }
                    else
                        DQ.push_back(To);
                }
            }
        }
    }
    return true;
}

long long Matrix[MAXN][MAXN];     // 邻接矩阵
long long Distance[MAXN];         // 源点到各点的最短路径

vector<Edge> Adjacency_Map[MAXN]; // 邻接表
bool in_Queue[MAXN];              // 顶点是否在队列中
int  in_Cnt[MAXN];                // 顶点入队次数

int main()
{
    Edge temp;
    int NodeSum;               //顶点数
    while (cin >> NodeSum)
    {
        int Source;
        cin >> Source;
        cin.ignore();
        
        for (int i = 1; i <= NodeSum; i++)
        {
            Adjacency_Map[i].clear(); //清空邻接表
            Matrix[i][0] = 0;         //清空邻接矩阵指示器
        }
        string str;
        for (int i(1); i <= NodeSum; ++i)
        {
            getline(cin, str);
            str += ' ';
            Make_Matrix(i, str, Matrix);
        }
        for (int From(1); From <= NodeSum; From++)
        {
            for (int To(1); To <= NodeSum; ++To)
            {
                if (From != To)
                {
                    temp.To     = To;
                    temp.Weight = Matrix[From][To];
                    Adjacency_Map[From].push_back(temp);
                }
            }
        }
        SPFA(Source, NodeSum, in_Queue, in_Cnt, Distance, Adjacency_Map);
        for (int i(1); i <= NodeSum; ++i)
        {
            if (i == Source)
            {
                continue;
            }
            cout << '(' << Source << " -> " << i << ") = " << Distance[i] << endl;
        }
    }
    return 0;
}