#include 
#include 
#include 
#include 
#include 
using namespace std;
struct node {
    int A, B, C;
    node(int a, int b, int c) {
        A = a;
        B = b;
        C = c;
    }
};
int main() {
    int n, m;
    cin >> n >> m;
    vector distance(n + 1, 2e9);
    vector graph;
    for(int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph.push_back(node(a, b, c));
    }
    int S;
    cin >> S;
    
    distance[S] = 0;
    for(int i = 0; i < n - 1; i++) {
        for(int j = 0; j < m; j++){
            int a =graph[j].A;
            int b = graph[j].B;
            int weight = graph[j].C;
            if(distance[a] != 2e9 and distance[a] + weight < distance[b]) {
                distance[b] = distance[a] + weight;
            }
            }
    }
    for(int i = 0; i < m; i++) {
        int a= graph[i].A;
        int b = graph[i].B;
        int weight = graph[i].C;
        if(distance[a] != 2e9 and distance[a] + weight < distance[b]) {
            cout << "ima negativen ciklus" << endl;
        }
    }
    for(int i = 0; i < n; i++) {
        cout << distance[i] << " ";
    }

    return 0;
}
5 9
0 1 4
0 2 2
1 2 3
2 1 1
1 4 2
1 3 4
2 4 3
2 3 5
3 4 -5