#include <iostream>

#include <cstring>

#include <queue>

using namespace std;

struct edge

{

    int v,w;

    edge*next;

};

edge*link[10001];

int d[10001],n,m,s,X,Y,Z;

bool v[10001];

queue<int>q;

void add(int u,int v,int w)

{

    edge*p=new edge;

    p->v=v;

    p->w=w;

    p->next=link[u];

    link[u]=p;

}

void digui(edge*p)

{

	if(p==NULL)return;

	if(p->next!=NULL)

		digui(p->next);

	delete p;

	p=NULL;

}

void remove()

{

	for(int i=1;i<=n;i++)

		digui(link[i]);

}

int main()

{

    cin >> n >> m >> s;//分别为顶点数 有向边数 源点

    for(int i=1;i<=m;i++)

    {

        cin >> X >> Y >> Z;//是有向边 x->y 长度z

        add(X,Y,Z);

    }

    q.push(s);

    v[s]=true;

    for(int i=1;i<=n;i++)

    	d[i]=2147483647;

    d[s]=0;

    while(!q.empty())

    {

        int x=q.front();

        q.pop();

        v[x]=false;

        for(edge*i=link[x];i!=0;i=i->next)

        {

            if(d[x]+i->w<d[i->v])

            {

                d[i->v]=d[x]+i->w;

                if(v[i->v]==false)

                {

                    v[i->v]=true;

                    q.push(i->v);

                }

            }

        }

    }

    for(int i=1;i<=n;i++)

    {

        cout << d[i] << ' ';

    }

    remove();

    return 0;

}