#include<bits/stdc++.h>
using namespace std;
const int N=5*1e5+10;
//typedef pair<int, int> PII;
int n,m,s;//点数 边数 起点位置 
int d[N];//存储每个点到起点距离 
int h[N],e[N],ne[N],w[N],idx;
bool st[N];//判断点有没在队列里面
//邻接表
void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
} 
void spfa(int s)
{
    memset(d,0x3f,sizeof d);//初始化为正无穷
    d[s]=0;//起点距离自己为0
  //  priority_queue<PII, vector<PII>,greater<PII>>q;
  queue<int>q;
    q.push(s);//点数
    st[s]=true;
    while(q.size())//while里面核心代码
    {
        auto t = q.front();
        q.pop();
       // int dist = t.first;int u = t.second;
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (d[j] > d[t] + w[i])
            {
                d[j] = d[t] + w[i];
                if (!st[j]) // 如果队列中已存在j，则不需要将j重复插入
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    //要求操作
   for(int i=1;i<=n;i++)
   {
       if(d[i]==0x3f3f3f3f)cout<<INT_MAX<<" ";
       else cout<<d[i]<<" ";
   }
}
int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m>>s;
    while(m--)
    {
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
     } 
     spfa(s);
     return 0;
 }