import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
import java.util.*;
class BellManFord {

    private final int INF = 1 << 27;
    private Integer dist[];
    private int parrtent[];
    private boolean negativCycle;

    public BellManFord(ArrayList<Edge> adj[], int source) {
        this.dist = new Integer[adj.length];
        this.parrtent = new int[adj.length ];
        this.negativCycle = false;
        this.shortestPath(adj, source);

    }

    private void shortestPath(ArrayList<Edge> graph[], int source) {
        int numberVertex = graph.length - 1;
        Queue<Integer> queue = new LinkedList<>();
        boolean[] inQueue = new boolean[graph.length];
        int[] visted = new int[graph.length];

				for(int i = 1; i < dist.length; i++){
            if(i == source){
                dist[i] = 0;
            }else {
                dist[i] = INF;
            }
						inQueue[i] = false;
						visted[i] = 0;
        }

        queue.add(source);
        inQueue[source] = true;
        while ( !queue.isEmpty() ){
            int current = queue.poll();
            inQueue[current] = false;

            for(Edge neighbor : graph[current]){
                if( dist[neighbor.getNode()] >= dist[current] + neighbor.getCost()){
                    dist[neighbor.getNode()] = dist[current] + neighbor.getCost();
                    parrtent[neighbor.getNode()] = current;

                    if(inQueue[neighbor.getNode()] == false){
                        inQueue[neighbor.getNode()] = true;

                        if(visted[neighbor.getNode()] > numberVertex){
                            negativCycle = true;
                            break;
                        }else {
                            queue.add(neighbor.getNode());
                            visted[neighbor.getNode()]++;
                        }
                    }
                }
            }

            if (negativCycle == true)
                break;
        }
    }

    public ArrayList<Integer> getMinDist(){
        if (this.negativCycle == true ){
            return new ArrayList<Integer>();
        }else {
            return new ArrayList<Integer>( Arrays.asList(dist));
        }
    }
}

class Edge {
	public int node;
	public int cost;

	Edge(int _node, int _cost) {
		node = _node;
		cost = _cost;
	}

	public int getNode() {
		return node;
	}

	public void setNode(int node) {
			this.node = node;
	}

	public int getCost() {
			return cost;
	}

	public void setCost(int cost) {
			this.cost = cost;
	}
}

public class Main {
	static class Task {
		public static final String INPUT_FILE = "bellmanford.in";
		public static final String OUTPUT_FILE = "bellmanford.out";

		int n;
		int m;
		int source;

		@SuppressWarnings("unchecked")
		ArrayList<Edge> adj[];

		private void readInput() {
			try {
				Scanner sc = new Scanner(new BufferedReader(new FileReader(
								INPUT_FILE)));
				n = sc.nextInt();
				m = sc.nextInt();
				source = sc.nextInt();
				adj = new ArrayList[n + 1];
				for (int i = 1; i <= n; i++)
					adj[i] = new ArrayList<>();
				for (int i = 1; i <= m; i++) {
					int x, y, w;
					x = sc.nextInt();
					y = sc.nextInt();
					w = sc.nextInt();
					adj[x].add(new Edge(y, w));
				}
				sc.close();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}

		private void writeOutput(ArrayList<Integer> result) {
			try {
				BufferedWriter bw = new BufferedWriter(new FileWriter(
								OUTPUT_FILE));
				StringBuilder sb = new StringBuilder();
				if (result.size() == 0) {
					sb.append("Ciclu negativ!\n");
				} else {
					for (int i = 1; i <= n; i++) {
						sb.append(result.get(i)).append(' ');
					}
					sb.append('\n');
				}
				bw.write(sb.toString());
				bw.close();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}

		private ArrayList<Integer> getResult() {
			return new BellManFord(adj, source).getMinDist();
		}

		public void solve() {
			readInput();
			writeOutput(getResult());
		}
	}

	public static void main(String[] args) {
		new Task().solve();
	}
}