// Bellman-Ford
// 1.初始化d[s] = 0,d[其他点] = inf
// 2.进行多轮循环,每轮对每一条边尝试进行松弛操作
// 3.当在一轮循环中没有成功的松弛操作时,循环结束
// dijkstra是先找到离源点最近的没有找到最短路的点进行松弛操作
// 而Bellman-Ford则是对所有边都尝试松弛,步骤3跳出
#include <bits/stdc++.h>
#define inf INT_MAX;
using namespace std;

using ll = long long ;
const int N = 1e5 + 50 ;
int n,m,s;
struct edge {
	int v,w;
};
vector<edge>e[N];
int d[N];
bool flag;

void BellmanFord(int s) {
	for (int i = 0;i <= n; i++) d[i] = inf;
	d[s] = 0;
    for (int i = 1;i <= n; i++) { // 进行n轮循环
    	flag = false;
    	for (int u = 1;u <= n; u++) { // 对每一条边尝试松弛操作
    		//if (d[u] == inf) continue;
    		for (auto t:e[u]) {
    			int v = t.v;
    			int w = t.w;
    			if (d[v] > d[u] + w) {
    				d[v] = d[u] + w;
    				flag = true;
    			}
    		}
    	}
    	if (!flag) break; // 当在一轮循环中没有成功的松弛操作时,循环结束
    }
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
    cin >> n >> m >> s;
    for (int i = 1;i <= m; i++) {
    	int u,v,w; cin >> u >> v >> w;
    	e[u].push_back({v,w});
    }
    BellmanFord(s);
    for (int i = 1;i <= n; i++) cout << d[i] << " ";
	return 0;
}