#include<bits/stdc++.h>#define inf 2147483647using namespace  std;bool book [200004];int cnt=0;int head[200020];int n,m,qq;struct Edge{   int to,next,w;}e[2000005];struct Dis{     int to,w;}dis[20000];struct cmp1{   bool operator () (Dis &a,Dis &b){      return a.w>b.w;   }};priority_queue<Dis ,vector<Dis>, cmp1> q;void add(int a,int b,int c){     e[++cnt].to=b;     e[cnt].w=c;     e[cnt].next=head[a];     head[a]=cnt;}void dijkstra(int k){    for(int i=1;i<=n;i++)    {	   dis[i].to=i;	   dis[i].w=inf;	}	dis[k].w=0;	q.push(dis[k]);    book[0]=1;	while(!q.empty())	{	   Dis t=q.top();q.pop();	   int x=t.to; 	   if(book[x]) continue;	   book[x]=1;	   for(int i=head[x];i;i=e[i].next)	   {	      int j=e[i].to;		  if(dis[j].w>dis[x].w+e[i].w&&!book[j])	      {		     dis[j].w=dis[x].w+e[i].w;		     q.push(dis[j]);		  }	   }	}	}int main(){   cin>>n>>m>>qq;   int t1,t2,t3;   for(int i=1;i<=m;i++)   {      cin>>t1>>t2>>t3;      add(t1,t2,t3);   }   dijkstra(qq);   for(int i=1;i<=n;i++)     cout<<dis[i].w<<" ";   return 0;}