#include<cstdio>
#include<iostream>
#include<utility>
#include<queue>
const int maxn=100001;


using namespace std;

struct QWQ
{
	int next;
	int to;
	int w;
}edge[maxn];
int read()
{
	int x=0;int k=1;char c=getchar();
	while(c<'0'||c>'9') {if(c=='-')k=-1;c=getchar();	}
	while(c>'0'&&c<'9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x*k; 
} 
int n,m,s;
int head[maxn];
int dis[maxn];
int vis[maxn];
int sum_edge;
void add(int from,int to,int w)
{
	edge[++sum_edge].to=to;
	edge[sum_edge].next=head[from];
	edge[sum_edge].w=w;
	head[from]=sum_edge; 
}
void init()
{
	n=read();m=read();s=read();
	//cin>>n>>m>>s;
	for(int i=1;i<=m;i++)
	{
		int x=read();
		int y=read();
		int w1=read();
		//int x,y,w1;
		//cin>>x>>y>>w1;
		add(x,y,w1);
	}
}
void dijktra()
{
	for(int i=1;i<=n;i++)
	dis[i]=1e9;
	dis[s]=0;
	priority_queue<pair<int,int> > q;
	q.push(make_pair(0,s));
	int now;
	while(!q.empty())
	{
		now=q.top().second;
		q.pop();
		if(vis[now])
		continue;
		vis[now]=1;
		for(int i=head[now];i;i=edge[i].next)
		{
			int w=dis[i]+edge[i].w;
			int to=edge[i].to;
			if(dis[to]>w)
			{
				dis[to]=w;
				q.push(make_pair(-w,to));
			}
		}
	}
}
void outit()
{
	for(int i=1;i<=n;i++)
	cout<<dis[i]<<" ";  
}
int main()
{
	init();
	dijktra();
	outit();
	return 0;
}

调了很多遍了！！！！！