#include<cstdio>
#include<queue>
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int N=1e5+5;
int dis[N];
struct Vex{
	int v,d;
	bool operator <(const Vex& rhs)const{
		return d>rhs.d;
	}
}vex;
vector<Vex>G[N];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
void dij(int s)
{
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	priority_queue<Vex> pq;
	vex.v=s,vex.d=0;
	pq.push(vex);
	while(!pq.empty())
	{
		vex=pq.top();pq.pop();
		int u=vex.v,d=vex.d;
		for(int i=0;i<G[u].size();i++)
		{
			int v=G[u][i].v,w=G[u][i].d;
			if(d+w<dis[v])
			{
				dis[v]=d+w;
				vex.v=v,vex.d=dis[v];
				pq.push(vex);
			}
		}
	}
}
int n,m,s,u,v,w;
int main()
{
	n=read();m=read();s=read();
	for(int i=1;i<=m;i++)
	{
		u=read();v=read();w=read();
		G[u].push_back({v,w});
	}
	dij(s);
	for(int i=1;i<=n;i++)printf("%d ",dis[i]);
}