package bfs;

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;

public class Main 
{
	public static void bfs(int node, ArrayList<ArrayList<Integer>> adjacents) throws IOException
	{
		Queue<Integer> q = new ArrayDeque<Integer>();
		
		int[] costs = new int[adjacents.size()];
		
		for (int i = 1;i < costs.length; i++)
			costs[i] = -1;
		
		boolean[] visited = new boolean[costs.length];
		
		costs[node] = 0;
		visited[node] = true;
		
		q.add(node);
		
		int crtNode = -1;
		
		
		while (!q.isEmpty())
		{
			
			crtNode = q.poll();
			
//			System.out.println("crtNode " + crtNode);
			
			visited[crtNode] = true;
			
			for (int nextNode : adjacents.get(crtNode))
			{
				if (visited[nextNode])
					continue;
				
				costs[nextNode] = costs[crtNode] + 1;
				q.add(nextNode);
			}
			
//			System.out.println(q);
		}
		
		BufferedOutputStream outputStream = new BufferedOutputStream(new FileOutputStream("bfs.out"));
		
		for (int i = 1; i < costs.length; i++)
			outputStream.write((Integer.toString(costs[i]) + " ").getBytes());
		
		outputStream.close();
	}
	
	private static int readInt(BufferedInputStream inputStream) throws IOException
	{
		int c = 0;
		int n = 0;
		
		while ((c = inputStream.read()) != -1 && c >= '0' && c <= '9')
			n = n * 10 + (c - '0');
		
		return n;
	}
	
	public static void main(String[] args) throws IOException
	{
		BufferedInputStream inputStream = new BufferedInputStream(new FileInputStream("bfs.in"));
		
		
		int n = readInt(inputStream);
		int m = readInt(inputStream);
		int s = readInt(inputStream);
		
		ArrayList<ArrayList<Integer>> adjacents = new ArrayList<ArrayList<Integer>>(n);
		
		for (int i = 1; i <= n+1; i++)
			adjacents.add(new ArrayList<Integer>());
		
		readInt(inputStream);
		int x, y;
		
		for (int i = 0; i < m; i++)
		{
			x = readInt(inputStream);
			y = readInt(inputStream);
			
			adjacents.get(x).add(y);
			
			readInt(inputStream);
		}
		
		
		bfs(s, adjacents);
		
		
	}
}