#include <iostream>
#include <ctime>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <iomanip>
#include <stack>
using namespace std;
const int inf=999999999;
int head[200005];
int dis[1005],diss[1005];
int use[1005];
bool vis[1005],mark[1005];
int cnt,m,n,s;
struct star{
int next,to,w;
}edge[200005];
void Init(){
memset(dis,127,sizeof(dis));
memset(vis,0,sizeof(vis));
memset(use,0,sizeof(use));
cnt=0;
}
void spfa(int u){
queue<int>q;
q.push(u);
dis[u]=0;vis[u]=1;
while(!q.empty()){
int x;
x=q.front();
q.pop();
for(int i=head[x];~i;i=edge[i].next){
if(dis[edge[i].to]>dis[x]+edge[i].w){
mark[edge[i].to]=1;
dis[edge[i].to]=dis[x]+edge[i].w;

if(!vis[edge[i].to]){
q.push(edge[i].to);
vis[edge[i].to]=1;
use[edge[i].to]++;
if(use[edge[i].to]>n){
printf("-1\n");
exit(0);
}
}
}
}
vis[x]=0;
}
return;
}
void save(int u,int v,int w){
edge[cnt].next=head[u];
edge[cnt].to=v;
edge[cnt].w=w;
head[u]=cnt++;
}
int main (){
memset(head,-1,sizeof(head));
memset(mark,0,sizeof(mark));
memset(diss,127,sizeof(diss));
Init();
int u,v,w;
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
save(u,v,w);
}

spfa(s);
mark[s]=1;
for(int i=1;i<=n;i++)diss[i]=dis[i];
for(int i=1;i<=n;i++){
if(!mark[i]){
Init();
spfa(i);
}
}
for(int i=1;i<=n;i++){
if(diss[i]<inf)printf("%d\n",diss[i]);
else printf("NoPath\n");
}
return 0;
}