#include <bits/stdc++.h>
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
using namespace std;
struct Edge
{
    ll to , w;
};
struct Node
{
    ll id , d;

    bool operator < (const Node &a) const
    {
        return a.d < d;
    }
};
int n , m , s;
ll u , v , w , dis[100005];
vector<Edge> e[100005];
bool book[100005];
int main()
{
    cin >> n >> m >> s;
    for (int i = 1 ; i <= m ; i++)
    {
        cin >> u >> v >> w;
        e[u].push_back({v , w});
        e[v].push_back({u , w});
    }

    for (int i = 1 ; i <= n ; i++) dis[i] = INF;
    dis[s] = 0;
    priority_queue<Node> pq;
    pq.push({s , 0});
    while (!pq.empty())
    {
        Node now = pq.top();
        pq.pop();
        if (book[now.id]) continue;
        book[now.id] = 1;
        for (auto i : e[now.id])
            if (dis[i.to] > i.w + now.d)
            {
                dis[i.to] = i.w + now.d;
                if (!book[i.to]) pq.push({i.to , dis[i.to]});
            }
    }
    for (int i = 1 ; i <= n ; i++) cout << dis[i] << ' ';
    return 0;
}

52 pts，WA#1，#3，#4.