#include<fstream>
#define Inf 999999999
#define Nmax 50099
#define Mmax 250099
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,start,d[Nmax];
struct Muchie{int x,y,c;} a[Mmax];

void ReadInput()
{
    f>>n>>m>>start;
    for(int i=1;i<=m;i++)
    {
        f>>a[i].x>>a[i].y>>a[i].c;
        if(a[i].x==start) d[a[i].y]=a[i].c;
    }

    for(int i=1;i<=n;i++) if(d[i]==0) d[i]=250001;
}

void PrintOutput()
{
    for(int i=1;i<=n;i++)
        {
            if(d[i]>=Inf || i==start)  g<<"0 ";
                               else    g<<d[i]<<" ";
        }
}

void Dijkstra()
{
    int gata=0;
    while(!gata)
    {
        gata=1;
        for(int i=1;i<=m;i++)
            if(d[a[i].y]>d[a[i].x]+a[i].c)
            {
                gata=0;
                d[a[i].y]=d[a[i].x]+a[i].c;
            }
    }
}

int main()
{
    ReadInput();
    Dijkstra();
    PrintOutput();
    f.close();g.close();
    return 0;
}