#include<cstdio>

#include<cstring>

#include<iostream>

#include<queue>

#include<cmath>

#include<vector>

using namespace std;

int n,m,s;

int dis[],first[];

inline void read(int &x)

{

    char c=getchar();

    int flag=; x=;

    while (c<''||c>'')

    {

        if (c=='-') flag=-;

        c=getchar();

    }

    while (c>=''&&c<='')

    {

        x=x*+c-'';

        c=getchar();

    }

    x*=flag;

}

struct edge

{

    int next,to,v;

    edge()

    {

    }

    edge(int a,int b,int c)

    {

        next=a; to=b; v=c;

    }

}E[];

struct heap

{

    int to,v;

    heap()

    {

    }

    heap(int a,int b)

    {

        to=a; v=b;

    }

};

priority_queue<heap> h;

inline bool operator < (const heap &a,const heap &b)

{

    return a.v>b.v;

}

int tot;

void add_to_edge(int a,int b,int c)

{

    E[++tot]=edge(first[a],b,c);

     first[a]=tot;

}

void add_to_heap(int p)

{

    for (int i=first[p]; i; i=E[i].next)

    {

        if (dis[E[i].to]==-)

        h.push(heap(E[i].to,dis[p]+E[i].v));

    }

}

void dijkstra(int s)

{

    while (!h.empty())

    {

        h.pop();

    }

    memset(dis,-,sizeof(dis));

    dis[s]=;

    add_to_heap(s);

    while (!h.empty())

    {

        if (dis[h.top().to]!=-)

        {

            h.pop();

            continue;

        }

        int p=h.top().to;

        dis[p]=h.top().v;

        h.pop();

        add_to_heap(p);

    }

}

int main()

{

    read(n); read(m); read(s);

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

    {

        int x,y,z;

        read(x); read(y); read(z);

        add_to_edge(x,y,z);

    }

    dijkstra(s);

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

    cout<<dis[i]<<" ";

    return ;

}