（只要输出一条）

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pr;
struct aty
{
	int next,to,num;
}edge[114514];
int n,m;
int s,t;
int dis[114514],from[114514];
int cnt=1;
void addedge(int a,int b,int c)
{
	edge[cnt].next=from[a];
	edge[cnt].to=b;
	edge[cnt].num=c;
	from[a]=cnt++;
}
void dijkstra(int s)
{
	priority_queue<pr,vector<pr>,greater<pr>>p;
	memset(dis,0x3f3f3f3f,sizeof(dis));
	dis[s]=0;
	p.push(pr(0,s));
	while(!p.empty())
	{
		pr q=p.top();
		p.pop();
		int u=q.second;
		if(dis[u]<q.first)
		    continue;
		if(u==t)
		    break;
		for(int i=from[u];i;i=edge[i].next)
		{
			int v=edge[i].to;
			if(dis[v]>dis[u]+edge[i].num)
			{
				dis[v]=dis[u]+edge[i].num;
				p.push(pr(dis[v],v));
			}
		}
	}
}
inline int read()
{
    int r=0,w=1;
    char ch=getchar(); 
    while(ch<'0' || ch>'9')
    {
        if(ch=='-')
		    w=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        r=r*(1<<3)+r*(1<<1)+ch-(1<<4)-(1<<5);
        ch=getchar();
    }
    return r*w;
}
signed main()
{
	ios::sync_with_stdio(false);
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n=read(),m=read(),s=read();
	for(int i=1;i<=m;i++)
	{
		int u=read(),v=read(),d=read();
		addedge(u,v,d);
	}
	dijkstra(s);
	for(int i=1;i<=n;i++)
	{
		cout<<dis[i]<<" ";
	}
	return 0;
}