#include<iostream>
#include<cstdlib>
#include<climits>
int graph[100][100];
using namespace std;
int mindist(bool mark[],int dist[],int n)
{
int minval = INT_MAX;
int index;
for(int i=0;i<n;i++)
{
if(mark[i] == false && dist[i]<minval)
{
minval = dist[i];
index = i;
}
}
return index;
}
void printsol(int dist[],int n)
{
for(int i=0;i<n;i++)
{
cout<<dist[i]<<endl;
}
}
void dijikstra(int src,int n)
{
int dist[100];
bool mark[100];
for(int i=0;i<n;i++)
{
dist[i] = INT_MAX;
mark[i] = false;
}
dist[src] = 0;
for(int count = 0;count<n-1;count++)
{
int u = mindist(mark,dist,n);
mark[u] = true;
for(int i=0;i<n;i++)
{
if(mark[i] == false && graph[u][i] && dist[u]!=INT_MAX && dist[i] > dist[u]+graph[u][i])
dist[i] = dist[u]+graph[u][i];
}
}
printsol(dist,n);
}
int main()
{
int n;
int src;
cin>>n;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>graph[i][j];
}
}
cin>>src;
dijikstra(src,n);
return 0;
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPGNzdGRsaWI+CiNpbmNsdWRlPGNsaW1pdHM+CmludCBncmFwaFsxMDBdWzEwMF07CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmludCBtaW5kaXN0KGJvb2wgbWFya1tdLGludCBkaXN0W10saW50IG4pCnsKCWludCBtaW52YWwgPSBJTlRfTUFYOwoJaW50IGluZGV4OwoJZm9yKGludCBpPTA7aTxuO2krKykKCXsKCQlpZihtYXJrW2ldID09IGZhbHNlICYmIGRpc3RbaV08bWludmFsKQoJCXsKCQkJbWludmFsID0gZGlzdFtpXTsKCQkJaW5kZXggPSBpOwoJCX0KCX0KCXJldHVybiBpbmRleDsKfQp2b2lkIHByaW50c29sKGludCBkaXN0W10saW50IG4pCnsKCWZvcihpbnQgaT0wO2k8bjtpKyspCgl7CgkJY291dDw8ZGlzdFtpXTw8ZW5kbDsKCX0KfQp2b2lkIGRpamlrc3RyYShpbnQgc3JjLGludCBuKQp7CglpbnQgZGlzdFsxMDBdOwoJYm9vbCBtYXJrWzEwMF07Cglmb3IoaW50IGk9MDtpPG47aSsrKQoJewoJCWRpc3RbaV0gPSBJTlRfTUFYOwoJCW1hcmtbaV0gPSBmYWxzZTsKCX0KCWRpc3Rbc3JjXSA9IDA7Cglmb3IoaW50IGNvdW50ID0gMDtjb3VudDxuLTE7Y291bnQrKykKCXsKCQlpbnQgdSA9IG1pbmRpc3QobWFyayxkaXN0LG4pOwoJCW1hcmtbdV0gPSB0cnVlOwoJCWZvcihpbnQgaT0wO2k8bjtpKyspCgkJewoJCQlpZihtYXJrW2ldID09IGZhbHNlICYmIGdyYXBoW3VdW2ldICYmIGRpc3RbdV0hPUlOVF9NQVggJiYgZGlzdFtpXSA+IGRpc3RbdV0rZ3JhcGhbdV1baV0pCgkJCWRpc3RbaV0gPSBkaXN0W3VdK2dyYXBoW3VdW2ldOwoJCX0KCX0KCXByaW50c29sKGRpc3Qsbik7Cn0KaW50IG1haW4oKQp7CglpbnQgbjsKCWludCBzcmM7CgljaW4+Pm47Cglmb3IoaW50IGk9MDtpPG47aSsrKQoJewoJCWZvcihpbnQgaj0wO2o8bjtqKyspCgkJewoJCQljaW4+PmdyYXBoW2ldW2pdOwoJCX0KCX0KCWNpbj4+c3JjOwoJZGlqaWtzdHJhKHNyYyxuKTsKCXJldHVybiAwOwp9
OQowIDQgMCAwIDAgMCAwIDggMAo0IDAgOCAwIDAgMCAwIDExIDAKMCA4IDAgNyAwIDQgMCAwIDIKMCAwIDcgMCA5IDE0IDAgMCAwCjAgMCAwIDkgMCAxMCAwIDAgMAowIDAgNCAwIDEwIDAgMiAwIDAKMCAwIDAgMTQgMCAyIDAgMSA2CjggMTEgMCAwIDAgMCAxIDAgNwowIDAgMiAwIDAgMCA2IDcgMAow
9
0 4 0 0 0 0 0 8 0
4 0 8 0 0 0 0 11 0
0 8 0 7 0 4 0 0 2
0 0 7 0 9 14 0 0 0
0 0 0 9 0 10 0 0 0
0 0 4 0 10 0 2 0 0
0 0 0 14 0 2 0 1 6
8 11 0 0 0 0 1 0 7
0 0 2 0 0 0 6 7 0
0