package spfa負(fù)權(quán)路徑;
 
import java.awt.List;
import java.util.ArrayList;
import java.util.Scanner;
public class SPFA {
 /**
  * @param args
  */
 public long[] result;   //用于得到第s個頂點到其它頂點之間的最短距離
 //數(shù)組實現(xiàn)鄰接表存儲
 class edge{
  public int a;//邊的起點
  public int b;//邊的終點
  public int value;//邊的值
  public edge(int a,int b,int value){
   this.a=a;
   this.b=b;
   this.value=value;
  }
 }
 public static void main(String[] args) {
  // TODO Auto-generated method stub
  SPFA spafa=new SPFA();
  Scanner scan=new Scanner(System.in);
  int n=scan.nextInt();
  int s=scan.nextInt();
  int p=scan.nextInt();
  edge[] A=new edge[p];
  for(int i=0;i<p;i++){
   int a=scan.nextInt();
   int b=scan.nextInt();
   int value=scan.nextInt();
   A[i]=spafa.new edge(a,b,value);
  }
  if(spafa.getShortestPaths(n,s,A)){
   for(int i=0;i<spafa.result.length;i++){
    System.out.println(spafa.result[i]+" ");
   }
  }else{
   System.out.println("存在負(fù)環(huán)");
  }
 }
 /*
  * 參數(shù)n:給定圖的頂點個數(shù)
  * 參數(shù)s:求取第s個頂點到其它所有頂點之間的最短距離
  * 參數(shù)edge:給定圖的具體邊
  * 函數(shù)功能：如果給定圖不含負(fù)權(quán)回路，則可以得到最終結(jié)果，如果含有負(fù)權(quán)回路，則不能得到最終結(jié)果
  */
 private boolean getShortestPaths(int n, int s, edge[] A) {
  // TODO Auto-generated method stub
  ArrayList<Integer> list = new ArrayList<Integer>();
  result=new long[n];
  boolean used[]=new boolean[n];
  int num[]=new int[n];
  for(int i=0;i<n;i++){
   result[i]=Integer.MAX_VALUE;
   used[i]=false;
  }
  result[s]=0;//第s個頂點到自身距離為0
  used[s]=true;//表示第s個頂點進入數(shù)組隊
  num[s]=1;//表示第s個頂點已被遍歷一次
  list.add(s); //第s個頂點入隊
  while(list.size()!=0){
   int a=list.get(0);//獲取數(shù)組隊中第一個元素
   list.remove(0);//刪除數(shù)組隊中第一個元素
   for(int i=0;i<A.length;i++){
   //當(dāng)list數(shù)組隊的第一個元素等于邊A[i]的起點時
    if(a==A[i].a&&result[A[i].b]>(result[A[i].a]+A[i].value)){
     result[A[i].b]=result[A[i].a]+A[i].value;
     if(!used[A[i].b]){
      list.add(A[i].b);
      num[A[i].b]++;
      if(num[A[i].b]>n){
       return false;
      }
      used[A[i].b]=true;//表示邊A[i]的終點b已進入數(shù)組隊
     }
    }
   }
   used[a]=false; //頂點a出數(shù)組對
  }
  return true;
 }
}