#include<bits/stdc++.h> using namespace std; struct ee { int z; int zz; int fa; }ed[1000000]; int sum=0,n,m,s,tou[20000]; bool vt[20000]={0}; long long ds[20000]; int main() { int a,b,c,i; cin>>n>>m>>s; for(i=1;i<=n;i++) { ds[i]=2147483647; } for(i=0;i<m;i++) { cin>>a>>b>>c; sum++; ed[sum].z=b; ed[sum].zz=c; ed[sum].fa=tou[a]; tou[a]=sum; } int rr=s; ds[s]=0; long long minn; while(!vt[rr]) { vt[rr]=true; for(i=tou[rr];i!=0;i=ed[i].fa) { if(!vt[ed[i].z]&&ds[ed[i].z]>ds[rr]+ed[i].zz) ds[ed[i].z]=ed[i].zz+ds[rr]; } minn=2147483647; for(i=1;i<=n;i++) { if(!vt[i]&&minn>ds[i]) { minn=ds[i]; rr=i; } } } for(int i=1;i<=n;i++) { cout<<ds[i]<<" "; } return 0; }