//Acest program a fost facut la ora 11:32
//este bellama-FORD fara STL
#include <cstdio>
#include <fstream>
#define inff 0x3f3f3f
#define MAX_N 100001

using namespace std;

struct nod
{
    int dest, cost;
    nod * next;
}*V[MAX_N],*U[MAX_N];


struct nodd
{
    int inf;
    nodd* next;
}*Q,*U2;


char viz[MAX_N];
int N,M,D[MAX_N],lol;

void baga(nod *&u,nod *&V,int poz,int c)
{
    nod *nou=new nod;
    nou->dest=poz;
    nou->cost=c;
    nou->next=NULL;
    if (!V)
        V=nou;
    else
        u->next=nou;
    u=nou;

}


void stergere(nodd *&p)
{
    nodd *x=p;
    p=p->next;
    delete x;
}


void baga2(nodd *&u,nodd *&V,int poz)
{
    nodd *nou=new nodd;
    nou->inf=poz;
    nou->next=NULL;
    if (!V)
        V=nou;
    else
        u->next=nou;
    u=nou;

}

void citire()
{
    int x,y,z;
    scanf("%d %d %d",&N,&M,&lol);
    for(int i = 1; i <= M; ++i)
    {
        scanf("%d %d",&x,&y);
        z=1;
        baga(U[x],V[x],y,z);
    }
}

void solve()
{
    memset(D, inff, sizeof D);

    baga2(Q,U2,lol);
    D[lol] = 0;
    viz[lol] ='1';
    while(Q)
    {
        int noddd = Q->inf;
        stergere(Q);
        viz[noddd]='0';
        for(nod *p=V[noddd];p;p=p->next)
            if(D[p->dest]>D[noddd]+p->cost)
            {
                D[p->dest]=D[noddd]+p->cost;
                if(viz[p->dest]!='1')
                {
                    baga2(U2,Q,p->dest);
                    viz[p->dest]='1';
                }
            }
    }
}
void afisare()
{
    for(int i = 1; i <= N; ++i)
        if (i!=lol)
            printf("%d ",(D[i]>inff?-1:D[i]));
        else
            printf("0 ");
    printf("\n");
}

int main()
{
    freopen ("bfs.in","r",stdin);
    freopen ("bfs.out","w",stdout);
    citire();
    solve();
    afisare();
    return 0;
}