#include<bits/stdc++.h>
using namespace std;

const int maxn=10000+10;
int dis[maxn][maxn];
struct node
{
	int id;
	int from;
	node(int x,int y)
	{
		id=x;from=y;
	}
	friend bool operator<(const node &a , const node &b)
    {
        return dis[a.from][a.id]>dis[b.from][b.id];   // ascending sort
    }
};

int n,m,s;
bool boolean[maxn];//标记节点是否确定了最短路径
int d[maxn];//从源点到点i的最短路径 
priority_queue <node> q;

int u[maxn];
int v[maxn];
int fir[maxn];
int next[maxn];

int minn(int x,int y)
{
	return x<=y?x:y;
}

int main()
{
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++)d[i]=2*1000000000;
	for(int i=1;i<=m;i++)
	{
		int lu,lv,w;
		cin>>lu>>lv>>w;
		if(lu==lv)continue ;
		if(!dis[lu][lv])
		{
			u[i]=lu;
			v[i]=lv;
			next[i]=fir[lu];
			fir[lu]=i;
			dis[lu][lv]=w;
		}
		else
			if(w<dis[lu][lv])dis[lu][lv]=w;
		
	}
	boolean[s]=true;
	d[s]=0;
	q.push(node(s,s));
	while(!q.empty())
	{
		node t=q.top();
		q.pop();
		if(boolean[t.id]==false)d[t.id]=minn(d[t.id],d[t.from]+dis[t.from][t.id]);
		boolean[t.id]=true;
		int k=fir[t.id];
		while(k!=0&&boolean[v[k]]==false)
		{
			q.push(node(v[k],u[k]));
			k=next[k];
		}
	}
	for(int i=1;i<=n;i++)cout<<d[i]<<' ';
	return 0;
}

1ac 3wr 1mle 5re