#include <bits/stdc++.h>

using namespace std;
// 使用 long long 防止路径总长度超过 int 范围（约 20 亿）
using ll = long long;

// 定义一个极大的数表示“无穷大”。
// 0x3f3f3f3f3f3f3f3f 在 long long 下是一个非常大的数，
// 且两个这样的数相加一般不会溢出，非常适合做最短路的初始值。
constexpr ll inf = 0x3f3f3f3f3f3f3f3f;

// Edge 结构体有两个用途：
// 1. 在邻接表 adj 中：u 表示邻接点编号，w 表示边的权重。
// 2. 在优先队列 q 中：u 表示节点编号，w 表示从起点 s 到 u 的当前最短距离。
struct Edge {
int u;
ll w;

// 重载小于号运算符，用于优先队列的排序。
// C++ 的 priority_queue 默认是“大根堆”（最大值在堆顶）。
// 我们需要“小根堆”（距离最小的在堆顶），所以这里逻辑反过来：
// 如果当前 w 大于对方的 w，则认为优先级更低。
bool operator< (const Edge& o) const {
return w > o.w;
}
};

int main() {
// 关闭输入输出同步流，提高 cin/cout 的读写速度，防止 TLE（超时）
ios::sync_with_stdio(false);
cin.tie(nullptr);

int n, m, s;
cin >> n >> m >> s; // 输入点数 n，边数 m，起点 s

// 邻接表存储图，adj[u] 存储的是从 u 出发的所有边
vector<vector<Edge> > adj(n + 1);

// 读入 m 条边
for (int i = 1; i <= m; ++i) {
int u, v;
ll w;
cin >> u >> v >> w;
// 无向图，所以要双向建边
adj[u].push_back({v, w}); // u -> v 权重 w
adj[v].push_back({u, w}); // v -> u 权重 w
}

// 优先队列（小根堆），存储 pair {节点 u, 距离 w}
// 堆顶永远是当前未确定的点中，距离起点最近的那个点
priority_queue<Edge> q;

// dist 数组：存储起点 s 到各个点的最短距离，初始化为无穷大
vector<ll> dist(n + 1, inf);

// vis 数组：标记某个点是否已经确定了最短路（是否被“出队”过）
vector<bool> vis(n + 1, false);

// 初始状态：起点 s 到自己的距离为 0
q.push({s, 0});
dist[s] = 0;

// Dijkstra 主循环
while (!q.empty()) {
// 取出堆顶元素（当前距离起点最近的点）
Edge now = q.top();
q.pop();

int u = now.u; // 当前节点编号

// 如果该点已经被访问过（即已经确定了最短路），则跳过。
// 这是因为同一个点可能多次入队（每次发现更短路径都会入队），
// 只有第一次出队时的距离才是最短的。
if (vis[u])
continue;

// 标记该点已确定最短路
vis[u] = true;

// 遍历 u 的所有邻接点（扫描出边）
for (int i = 0; i < adj[u].size(); ++i) {
int v = adj[u][i].u; // 邻接点 v
ll w = adj[u][i].w; // 边 u-v 的权重

// 松弛操作 (Relaxation)：
// 如果经由 u 到达 v 的距离（dist[u] + w）比当前记录的 dist[v] 更短
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w; // 更新 v 的最短距离
q.push({v, dist[v]}); // 将更新后的 v 放入队列，以便后续扩展
}
}
}

// 输出从起点 s 到所有点 1~n 的最短距离
for (int i = 1; i <= n; ++i) {
cout << dist[i] << " ";
}
cout << "\n";

return 0;
}