#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
using namespace std;
namespace wzl{
int n,m,s;
const int inf = 1e9+1;
vector <int>head,cnt,nxt,to,fr,dis,wt;
vector <bool>vis; 
queue <int>q;
inline void add(int u, int v,int w){
	wt.push_back(w);
	to.push_back(v);
	fr.push_back(u);
	nxt.push_back(head[u]);
	head[u] = wt.size() - 1;
	return;
}
bool spfa(){
	dis[s] = 0;
	q.push(s);
	vis[s] = true;
	while(q.size()){
		int u = q.front();
		q.pop();
		vis[u] = false;
		for(int i = head[u]; i != -1; i = nxt[i]){
			int v = to[i], w = wt[i];
			if(dis[v] > dis[u] + w){
				dis[v] = dis[u] + w;
				if(vis[v] == false){
					q.push(v); vis[v] = true;
				}
				cnt[v] = cnt[u] + 1;
				if(cnt[v] >= n){
					return false;
				}
			}
		}
	}
	return true;
	
	
}
void main(){
//	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>m>>s;
	
	head.resize(n+1,-1); dis.resize(n+1,inf); vis.resize(n+1,false);
	
	for(int i = 1; i <= m; ++i){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
	}
	
	bool ans = spfa();
//	cout<<"#";
	if(ans == false){
		cout<<"无解"<<endl;return;
	}
	for(int i = 1; i <= n; ++i){
		
			cout<<dis[i]<<' ';
	
		
	}
}
}


int main(){
	wzl::main();
	return 0;
}

qaq