#include<stdio.h>
#include<limits.h>
struct Edge{
    int u,v,w;
};
int main(){
int n,m;
  scanf("%d %d",&n,&m);
  
  struct Edge edges[m];
  for(int i = 0;i<m;i++){
  scanf("%d %d %d",&edges[i].u,&egdes[i].v,&edges[i].w);
    }
    int src;
    scanf("%d",&src);
    
    int dist[n];
    for (int i=0;i<n;i++)
       dist[i] = INT_MAX;
    dist[src]=0;
      
      
    for(int i=1;i<n-1;i++){
         for(int j=0;j<m;j++){
             int u=edges[j].u;
             int v=edges[j].v;
             int w=edges[j].w;
             if(dist[u]! =INT_MAX && dist[u] + w < dist[v])
             dist[v]=dist[u]+w;
         }
    }
    
     for (int j=1;j<m;j++){
         for (int j=0;j<m;j++){
             int u=edges[j].u;
             int v=edges[j].v;
             int w=edges[j].w;
             if(dist[u]! =INT_MAX && dist[u] + w < dist[v]){
             printf("Graph contains a negative weight cycle\n");
             return 0;
            
         }
     }

for(int i=0;i<m;i++){
    if(dist[i]==INT_MAX)
    printf("INF ");
    else
    printf("%d",dist[i]);
}
    printf("\n");
    return 0;
 }