#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
inline int getint(){
	char ch;long long w=0,f=1;ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-') f=-f;ch=getchar();}
	while(ch>='0' && ch<='9'){w=(w<<1)+(w<<3)+(ch^48);ch=getchar();}
	return w*f;
}
int u[200005],w[200005],dis[100005],head[200005],nxt[200005],tot;
bool vis[100005];
void add(int x,int y,int v)
{
	tot++;
	u[tot]=y;
	w[tot]=v;
	nxt[tot]=head[x];
	head[x]=tot;
}
int n,m,start;
void Dijkstra(int start)
{
	for(int i=1;i<=n;i++)
	{
		int minn=1e9,mini;
		for(int j=1;j<=n;j++)
		{
			if(!vis[j] && minn>dis[j])
			{
				vis[j]=true;
				minn=dis[j];
				mini=j;
			}
		}
		for(int j=head[mini];j;j=nxt[j])
			dis[u[j]]=min(dis[u[j]],dis[mini]+w[j]);
	}
	dis[start]=0;
	for(int i=1;i<=n;i++)
		cout<<dis[i]<<" ";
}
int main()
{
	memset(dis,0x7f,sizeof(dis));
	cin>>n>>m>>start;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
		if(u==start) dis[v]=w;
	}
	Dijkstra(start);
	return 0;
}

现在是O(n²)算法，但是结果不太对