1 #include<cstdio>

 2 #include<cstdlib>

 3 #include<cstring>

 4 #include<iostream>

 5 #include<queue>

 6 using namespace std;

 7 typedef long long LL;

 8

 9 const int N=10010,M=500010;

10 const LL INF=2147483647;

11 int n,m,st,len=0;

12 int vis[N],last[N];

13 LL dis[N];

14 struct edge{int x,y,next;LL d;}a[2*M];

15 queue<int> q;

16

17 void ins(int x,int y,LL d)

18 {

19     a[++len].x=x,a[len].y=y,a[len].d=d;

20     a[len].next=last[x],last[x]=len;

21 }

22 void spfa()

23 {

24     for (int i=1;i<=n;i++) dis[i]=INF;

25     memset(vis,0,sizeof(vis));

26     while (!q.empty()) q.pop();

27     dis[st]=0, vis[st]=1;

28     q.push(st);

29     while (!q.empty())

30     {

31       int x=q.front();

32       q.pop(); vis[x]=0;

33       for (int i=last[x];i;i=a[i].next)

34       {

35         int y=a[i].y;

36         if (dis[x]+a[i].d<dis[y])

37         {

38           dis[y]=dis[x]+a[i].d;

39           if (!vis[y]) vis[y]=1, q.push(y);

40         }

41       }

42     }

43 }

44 int main()

45 {

46     scanf("%d%d%d",&n,&m,&st);

47     int x,y; LL d;

48     memset(last,-1,sizeof(last));

49     for (int i=1;i<=m;i++)

50     {

51       scanf("%d%d%lld",&x,&y,&d);

52       ins(x,y,d);

53     }

54     spfa();

55     for (int i=1;i<=n;i++)

56       printf("%lld ",dis[i]);

57     printf("\n");

58     return 0;

59 }