#include <bits/stdc++.h>
#define inf 0x7f7f7f7f
using namespace std;
class Edge
{
public:
int l,r,nextline;
long long val;
}eline[4000000];
class Number
{
public:
int n;
long long v;
};
priority_queue<Number> won;
bool visited[800000];
int elast[800000],n,m;
long long dis[800000];
bool operator<(Number L,Number R)
{
return L.v>R.v;
}
int main()
{
//最短路默写2
int s,i,j;
scanf("%d%d%d",&n,&m,&s);
for(i=1;i<=n;i++) dis[i]=inf;
for(i=1;i<=m;i++)
{
scanf("%d%d%lld",&eline[i].l,&eline[i].r,&eline[i].val);
eline[i].nextline=elast[eline[i].l];
elast[eline[i].l]=i;
}
dis[s]=0;
Number _now;
_now.v=0,_now.n=s;
won.push(_now);
while(!won.empty())
{
_now=won.top();
won.pop();
if (visited[_now.n]) continue;
if (_now.n==n) break;
visited[_now.n]=true;
for(i=elast[_now.n];i!=0;i=eline[i].nextline)
if (dis[eline[i].r]>dis[_now.n]+eline[i].val)
{
dis[eline[i].r]=dis[_now.n]+eline[i].val;
Number temp;
temp.v=dis[eline[i].r];
temp.n=eline[i].r;
won.push(temp);
}
}
for(i=1;i<=n;i++) printf("%lld ",dis[i]);
}