#include <iostream>

 #include <algorithm>

 #include <cstdio>

 #include <string>

 #include <cstring>

 #include <cmath>

 #include <queue>

 #define N 100010

 #define M 100010

 //复杂度上限m*n

 //n个点，每个如m次 

 //正常nlogn

 //网格图贼慢

 using namespace std;

 queue <int> z;

 int d[N],len,visit[N],n,m;

 //采用结构体存图

 struct edge

 {

     int x,y,k,next;

 }a[M];

 // 邻接链表存储

 int first[M];

 void ins(int x,int y,int k)

 {

     len++;

     a[len].x=x;

     a[len].y=y;

     a[len].k=k;

     a[len].next=first[x];

     first[x]=len;

 }

 int sum[N];

 int main()

 {

     cin>>n>>m;

     memset(d,,sizeof(d));//63是billion（十亿）级别的10 6110 9567

     int x,y,k;

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

     {

         cin>>x>>y>>k;

         ins(x,y,k);

         ins(y,x,k);

     }

     int s;

     cin>>s;//源点

     z.push(s);

     visit[s]=;

     d[s]=;

     //******主体代码

     while(!z.empty())

     {

         x=z.front();

         for(int k=first[x];k;k=a[k].next)

         {

             y=a[k].y;

             if(d[x]+a[k].k < d[y])

             {

                 d[y]=d[x]+a[k].k;

                 if(!visit[y])

                 {

 //                    sum[y]++;

                     z.push(y);//这是一个迭代的过程（老师说的，其实我不知道啥是迭代）

                     visit[y]=;

                 }

             }

         }

         z.pop();

         sum[x]++;

         /*if(sum[x] > 2*m)//判断负环 有时会用到

         {

             printf("NO");

             break;

         }*/

         visit[x]=;

     }

     //**********

     for(int i=;i<=n;i++)    cout<<d[i]<<" ";//得到所有节点到源点的最短路

     return ;

 }