import java.util.*;

// Class to represent a weighted directed graph
class Graph {
    private int V; // Number of vertices
    private List<Edge> adj; // List of adj

    // Constructor
    public Graph(int V) {
        this.V = V;
        adj = new ArrayList<>();
    }

    // Class to represent an edge
    class Edge {
        int src, dest, weight;

        Edge(int src, int dest, int weight) {
            this.src = src;
            this.dest = dest;
            this.weight = weight;
        }
    }

    // Add an edge to the graph
    public void addEdge(int src, int dest, int weight) {
        adj.add(new Edge(src, dest, weight));
    }

    // Bellman-Ford algorithm to find shortest paths from source vertex
    public void bellmanFord(int source) {
        // Initialize distances from source to all vertices as INFINITY
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[source] = 0;

        // Relax all adj V-1 times
        for (int i = 0; i < V - 1; i++) {
            for (Edge edge : adj) {
                int u = edge.src;
                int v = edge.dest;
                int weight = edge.weight;
                if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                }
            }
        }

        // Check for negative weight cycles
        for (Edge edge : adj) {
            int u = edge.src;
            int v = edge.dest;
            int weight = edge.weight;
            if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
                System.out.println("Graph contains negative weight cycle");
                System.out.println("-1");
                return;
            }
        }

        // Print shortest distances
        System.out.println("Shortest distances from source vertex " + source + ":");
        for(int i = 0; i < V; ++i)
		    if(dist[i]!=Integer.MAX_VALUE)
			    System.out.print(dist[i]+" ");
		    else
		        System.out.print(-1+" ");
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int V = scanner.nextInt();
        Graph graph = new Graph(V);
        int E = scanner.nextInt();
        for (int i = 0; i < E; i++) {
            int src = scanner.nextInt();
            int dest = scanner.nextInt();
            int weight = scanner.nextInt();
            graph.addEdge(src, dest, weight);
        }
        int source = scanner.nextInt();
        graph.bellmanFord(source);
        scanner.close();
    }
}