#include <bits/stdc++.h>
using namespace std;
const int N = 100001;
const int inf = 0x3f3f3f;
struct nod///优先队列存最小距离的点，以知开头，所以记录终点和长度 
{
    int end;
    int length;
};
struct nod1///用vector存零阶矩阵 
{
    int to;
    int len;
};
bool operator<(nod a, nod b)////优先队列小顶堆 
{
    return a.length < b.length;
}
priority_queue<nod>q;
vector<nod1>dp[N];
long long dis[N];/////dis是记录起点到对应点的最短距离 
int vis[N];/////vis记录这个点有没有走过 
int n, m, w;//////n是总共几个点，m是几组数据，s点到e的距离为d，w是起点 
void dijkstra()
{
    memset(dis, inf, sizeof(dis));//////领起点w到每个点的距离为无穷 
    memset(vis, 0, sizeof(vis));/////每个点都没被遍历过 
    dis[w] = 0;/////起点到起点的距离为0 
    nod y;
    y.end = w;
    y.length = 0;
    q.push(y); 
    while (!q.empty())
    {
        int top = q.top().end; 
        q.pop();
        if(vis[top])
        {
        	continue;
		}
        for(int i=0;i<dp[top].size();i++)
        {
            int end_ = dp[top][i].to;
            int length_ = dp[top][i].len;
            dis[end_] = min(dis[end_], dis[top] + length_);
            nod temp;
            temp.end = end_;
            temp.length = length_;
            q.push(temp);
        }
        vis[top] = 1;
    }
}
int main()
{
    cin >> n >> m >> w;
    for (int i = 1; i <= m; i++)
    {
        int s, e, d;
        cin >> s >> e >> d;
        nod1 t;
        t.to = e;
        t.len = d;
        dp[s].push_back(t);///s点到e点的距离为d 
    }
    dijkstra();
    for (int i = 1; i <= n; i++)
    {
        cout << dis[i] << " ";
    }
}