#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define repi(a,n) for(int i=(a);i<(n);++i)
const int maxn=1e6;
const int INF=1e9;
int n,m,s;
struct edge{
	int from,cost,to;
};
struct node{
	int u,v;
	bool operator<(const node& e)const
	{
		return v>e.v;
	}
};
int d[maxn],p[maxn];
bool used[maxn];
vector<int>g[maxn];
vector<edge>edges;
void inti(int n)
{
	for(int i=1;i<=n;++i) g[i].clear();
	edges.clear();
}
void add(int from,int cost,int to)
{
	edges.push_back((edge){from,cost,to});
	g[from].push_back(edges.size()-1);
}
void dij(int s)
{
	priority_queue<node>q;
	d[s]=0;
	for(int i=0;i<n;++i) d[i]=INF;
	memset(used,0,sizeof(used));
	q.push((node){s,0});
	while(!q.empty())
	{
		node e=q.top();q.pop();
		int  u=e.u;
		if(used[u]) continue;
		used[u]=1;
		int qwq=g[u].size();
		for(int i=0;i<qwq;++i)
		{
			edge& e=edges[g[u][i]];
			if(d[e.to]>d[e.from]+e.cost)
			{
				d[e.to]=d[e.from]+e.cost;
				p[e.to]=g[u][i];
				q.push(node({e.to,d[e.to]}));
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m>>s;
	inti(n);
	for(int i=0;i<m;++i)
	{
		int u,v,t;
		cin>>u>>v>>t;
		add(u,t,v);
	}
	dij(s);
	for(int i=1;i<=n;++i) cout<<d[i]<<" ";
	return 0;
}