#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;
struct vertex
{
vector<pair<int, int>> adj;
int dis;
int id;
bool known;
};
vertex G[10001];
auto cmp = [](int i, int j){return G[i].dis > G[j].dis;};
priority_queue<int, vector<int>, decltype(cmp)> Q(cmp);
int main()
{
int n, m, s;
cin >> n >> m >> s;
for (int i = 1; i <= n; i++)
G[i].id = i, G[i].dis = INT_MAX;
while (m--)
{
int v, w, c;
cin >> v >> w >> c;
G[v].adj.push_back({w, c});
}
G[s].dis = 0;
Q.push(s);
while (!Q.empty())
{
int t;
do
{
t = Q.top();
Q.pop();
} while(G[t].known && !Q.empty());
vertex & v = G[t];
v.known = true;
int len = v.adj.size();
for (int i = 0; i < len; i++)
{
vertex & w = G[v.adj[i].first];
if (!w.known)
{
int c = v.adj[i].second;
w.dis = min(w.dis, v.dis + c);
Q.push(w.id);
}
}
}
for (int i = 1; i <= n; i++)
cout << G[i].dis << ' ';
return 0;
}