#include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <queue>

 #include <algorithm>

 using namespace std;

 const int maxn=1e4+;

 int dist[maxn];

 bool vis[maxn];

 struct node

 {

     int d,len;

     ///相反

     bool operator<(const node & b) const

     {

         return b.len<len;    ///b.d放在左边，方便

     }

 };

 priority_queue<node> st;///这样写就可以了，省略后面的部分

 vector<pair<int,int> >e[maxn];

 int main()

 {

     int n,m,s,x,y,z,d,i;

     vector<pair<int,int> >::iterator j;

     scanf("%d%d%d",&n,&m,&s);

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

     {

         scanf("%d%d%d",&x,&y,&z);

         //有向边

         e[x].push_back(make_pair(y,z));

     }

     memset(dist,0x7f,sizeof(dist));

     dist[s]=;

     st.push({s,});

     ///点可以重复在priority_queue出现

     while ()

     {

         ///该点已被处理

         ///若st为空，执行st.top()会报错

         while (!st.empty() && vis[st.top().d])

             st.pop();

         ///必不可少

         if (st.empty())

             break;

         ///以dist[d]为点d的最短路为基础，进行拓展

         d=st.top().d;

         vis[d]=;///!

         st.pop();///!

         for (j=e[d].begin();j!=e[d].end();j++)

             if (dist[j->first]>dist[d]+j->second)

             {

                 dist[j->first]=dist[d]+j->second;

                 st.push({j->first,dist[j->first]});

             }

     }

     for (i=;i<=n;i++)

     {

         if (i!=)

             printf(" ");

         printf("%d",dist[i]==dist[]?:dist[i]);

     }

     return ;

 }

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <queue>

 #include <algorithm>

 using namespace std;

 const int maxn=5e3+;

 int ci=;

 ///次短路，可以推广位k短路(当然k要较小)，此时dist的第二维的大小需要增加，第二维的数据修改也要修改

 struct node

 {

     int d,len;

     node *next;

 }*e[maxn];

 struct rec

 {

     int d,dist;

     bool operator<(const rec &b) const

     {

         return b.dist<dist;

     }

 };

 priority_queue<rec> st;

 int hap[maxn],dist[maxn][];

 int main()

 {

     int i,a,b,c,n,m,d,dis,dd,ddis;

     node *p;

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

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

     {

         scanf("%d%d%d",&a,&b,&c);

         p=new node();

         p->d=b;

         p->len=c;

         p->next=e[a];

         e[a]=p;

         p=new node();

         p->d=a;

         p->len=c;

         p->next=e[b];

         e[b]=p;

     }

     ///from 1 to n

     memset(dist,0x7f,sizeof(dist));

     dist[][]=;

     st.push({,});

     while ()

     {

         while (!st.empty() && hap[st.top().d]==ci)

             st.pop();

         ///if not exists(not break in the next period)

         if (st.empty())

             break;

         ///确定了d,dist是第hap[d]小，以此为基础拓展其它点的第一小和第二小

         d=st.top().d;

         dis=st.top().dist;

         hap[d]++;

         st.pop();

         if (d==n && hap[d]==)

             break;

         p=e[d];

         while (p)

         {

             dd=p->d;

             ddis=dis+p->len;

             if (ddis<dist[dd][])

             {

                 dist[dd][]=dist[dd][];

                 dist[dd][]=ddis;

                 st.push({dd,ddis});///{d,dis[dd][1]}已经在优先队列里了

             }

             else if (ddis<dist[dd][])

             {

                 dist[dd][]=ddis;

                 st.push({dd,ddis});

             }

             p=p->next;

         }

     }

     ///if not exists

     printf("%d",dist[n][]);

     return ;

 }