//Dijkstra's algorithm
//program name "dijk.cpp"

#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdlib>

using namespace std;

int main(int argc, char *argv[]) {
	//変数の宣言。
	float mtx[20][20];
	float e;
	int n, i, j, s;
	float d[20];
	int t[20];

	//コマンドライン引数が２つでない場合は，使用法を表示して終了する。
	if (argc != 3) {
		cerr << "Usage: dijk <filename> <start>\n";
		return 1;
	}

	//ファイル１を開く。エラーの場合はその旨表示して終了する。
	ifstream fin1(argv[1]);
	if (!fin1) {
		cerr << "Can't open file1!\n";
		return 1;
	}

	//ファイル１の内容の読み込み。
	fin1 >> n;				//行列の行・列数の読み込み。
	for (j = 1; j <= n; j++) {
		for (i = 1; i <= n; i++) {
			fin1 >> mtx[i][j];	//行列各要素の読み込み。
		}
	}
	fin1.close();				//ファイル１を閉じる。

	s = atoi(argv[2]);

	for (j = 1; j <= n; j++){
		d[j] = 9999;
		t[j] = -1;
	}

	d[s] = 0;

	while (1){
		i = 0;
		e = 9999;
		for (j = 1; j <= n; j++){
			if (t[j] < 0 && d[j] < e){
				i = j;
				e = d[j];

			}
		}
		if (i <= 0) break;
		t[i] = 1;
		for (j = 1; j <= n; j++){
			if (d[j] >(d[i] + mtx[i][j])){
				d[j] = d[i] + mtx[i][j];
			}
		}
	
	}
	for (i = 1; i <= n; i++){
		cout << i << '\t' << d[i] << '\n';
	}

	return 0;		//戻り値として０を返す。
}			//プログラムの終わり。