#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
ifstream f("bfs.in");
ofstream g("bfs.out");
#define MAXN 100000
vector < pair <int, int > >G[MAXN];
priority_queue< pair<int, int> > pq;
int M, N, S,cost=1;
int v[MAXN];
int dist[MAXN];
int main()
{
    f>>N>>M>>S;
    memset(dist, 0x3f, sizeof(dist));
    dist[S] = 0;
    for(int i=1; i<=M; i++)
    {
        int node1,node2;
        f>>node1>>node2;
        G[node1].push_back(make_pair(node2,cost));
    }
    pq.push(make_pair(0,S));
    while(!pq.empty())
    {
        int node=pq.top().second;
        pq.pop();
        if(v[node]==1)
        {
            continue;
        }
        v[node]=1;
        for (int i = 0; i < G[node].size(); ++i)
        {
            if (dist[G[node][i].first] > dist[node] + G[node][i].second)
            {
                dist[G[node][i].first] = dist[node] + G[node][i].second;
                pq.push(make_pair(-dist[G[node][i].first], G[node][i].first));
            }
        }

    }
    for(int i=1; i<=MAXN; i++)
    {
        if(dist[i]>N)
            dist[i]=-1;
    }
    for(int i=1; i<=N; i++)
    {
        g<<dist[i]<<" ";
    }
}