import java.util.Scanner;

public class Main4 {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int m=sc.nextInt();
		int s=sc.nextInt();
		int[] w=new int[m];
		int[] v=new int[m];
		int[] u=new int[m];
		int[] dis=new int[n+1];//为s~n点的最短路径
		int[][] arr=new int[m][m];
		dis[s]=0;
		for(int i=0;i<m;i++) {
			u[i]=sc.nextInt();
			v[i]=sc.nextInt();
			w[i]=sc.nextInt();
			if(u[i]==s) {
				dis[v[i]]=w[i];
			}
			arr[u[i]][v[i]]=w[i];
		}
		for(int i=1;i<n;i++) {
			for(int j=i+1;j<=n;j++) {
			dis[j]=Math.min(dis[j], dis[i]+arr[i][j]);	
			}
		}
		for(int i=1;i<=n;i++) {
			System.out.print(dis[i]+" ");
		}
	}
}