wa#1，不知道为啥能错/yun

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define debug(...) fprintf(stderr,##__VA_ARGS__)

template<typename T>
void read(T &x){
	x=0;
	int f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') x=x*10+(int)(c-'0'),c=getchar();
	x*=f;
}

std::stack<char>st;
template<typename T>
void print(T x){
	if(x==0) putchar('0');
	if(x<0) putchar('-'),x=-x;
	while(st.size()) st.pop();
	while(x) st.push((char)('0'+x%10)),x/=10;
	while(st.size()) putchar(st.top()),st.pop();
}

template<typename T>
void printsp(T x){
	print(x),putchar(' ');
}

template<typename T>
void println(T x){
	print(x),putchar('\n');
}

template<typename T,typename I>
void chkmin(T &a,I b){
	a=std::min(a,b);
}

template<typename T,typename I>
void chkmax(T &a,I b){
	a=std::max(a,b);
}

bool Mbe;

const int inf=1e18,MOD1=998244353,MOD2=1e9+7;

const int maxn=1e5+10;

std::vector<std::pair<int,int> >a[maxn];

int n,m,s;

bool in[maxn];

int sum[maxn],dis[maxn],tot;

bool spfa(int s){
	int B=(int)(std::sqrt(tot));
	std::deque<int>q;
	for(int i=1;i<=n;i++) dis[i]=inf,in[i]=0;
	in[s]=1,dis[s]=0,q.push_front(s);
	while(q.size()){
		int x=q.front();
		q.pop_front();
		in[x]=0;
		if(++sum[x]>n+1) return 0;
		for(std::pair<int,int>p:a[x]){
			if(dis[p.fi]>dis[x]+p.se){
				dis[p.fi]=dis[x]+p.se;
				if(in[p.fi]) continue;
				in[p.fi]=1;
				if(!q.size()) q.push_back(p.fi);
				else if(dis[p.fi]>dis[q.front()]+B) q.push_back(p.fi);
				else q.push_front(p.fi);
			}
		}
	}
	return 1;
}

bool Men;

signed main(){
	debug("%.6lfMB\n",(&Mbe-&Men)/1048576.0);
	read(n),read(m),read(s);
	for(int i=1;i<=m;i++){
		int u,v,w;
		read(u),read(v),read(w);
		a[u].push_back({v,w});
		tot+=w;
	}
	// assert(tot<=1e9);
	spfa(s);
	for(int i=1;i<=n;i++) printsp(std::min(dis[i],215748364777ll));
	debug("%.6lfms\n",1e3*clock()/CLOCKS_PER_SEC);
}