#include <bits/stdc++.h>
#define N 100100
#define M 500000
#define il inline
#define in(a) a = read()
#define cl(a, b) memset(a, b, sizeof(a))
#define INF 0x7fffffff
#define MOD 10000007
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

il int read()
{
    char ch = getchar();
    int v = 1, x = 0;
    while (ch < '0' || ch > '9')
    {
        if (ch == '-') v = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return v * x;
}

il void out(int x)
{
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) out(x / 10);
    putchar(x % 10 + '0');
}

struct edge
{
    int y, w;
};

struct node
{
    int dis;
    bool find;
} d[N];

struct nodep
{
    int dis;
    int pos;
    bool operator <(const nodep &x) const
    {
        return x.dis < dis;
    }
};

vector<edge> mp[N];
priority_queue<nodep> q;
int n, m;

/*
void dij(int first)
{
    //--init--//
    for (int i = 1; i <= n; i++) d[i].dis = INF;
    int x = 0, minn = INF, y, w;
    d[first].dis = 0;
    for (int i = 1; i < n; i++)
    {
        minn = INF;
        for (int j = 1; j <= n; j++)
            if (!d[j].find && d[j].dis < minn) minn = d[j].dis, x = j;
        d[x].find=true;
        for (int j = 0; j < (int)mp[x].size(); j++)
        {
            y=mp[x][j].y,w=mp[x][j].w;
            d[y].dis=min(d[y].dis,d[x].dis+w);
        }
    }
}
*/

void dij(int first)
{
    for (int i = 1; i <= n; i++) d[i].dis = INF;
    d[first].dis = 0;
    int y, w;
    nodep temp;
    temp.dis=0,
    temp.pos=first;
    q.push(temp);
    while (!q.empty())
    {
        temp = q.top();
        q.pop();
        int x = temp.pos;
        if (d[x].find) continue;
        d[x].find = true;
        for (int i = 0; i < (int)mp[x].size(); i++)
        {
            y = mp[x][i].y, w = mp[x][i].w;
            if (d[y].dis > d[x].dis + w)
            {
                d[y].dis = d[x].dis + w;
                if (!d[y].find)
                {
                    temp.dis=d[y].dis;
                    temp.pos=y;
                    q.push(temp);
                }
            }
        }
    }
}

int main()
{
    int first, x, y, w;
    edge qwq;
    in(n), in(m), in(first);
    for (int i = 0; i < m; i++)
    {
        in(x), in(y), in(w);
        qwq.y = y, qwq.w = w;
        mp[x].push_back(qwq);
    }
    dij(first);
    for (int i = 1; i <= n; i++)
    {
        out(d[i].dis);
        printf(" ");
    }
    cout << endl;
    return 0;
}