#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MN = 6047;
const long long INF = 1e18 + 42;

int n, m, s;
vector<vector<pair<int, long long>>> vert(MN);
int not_shortest[MN];
int relaxed[MN];
int not_reached[MN];

void dfs(int src) {
    not_shortest[src] = 1;
    for (int i = 0; i < vert[i].size(); i++) {
        int k = vert[src][i].first;
        if (!not_shortest[k]) {
            dfs(k);
        }
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m >> s;
    --s;
    for (int i = 0; i < m; i++) {
        int a, b;
        long long w;
        cin >> a >> b >> w;
        vert[--a].emplace_back(make_pair(--b, w));
    }
    for (int i = 0; i <= n; i++) {
        not_shortest[i] = 0;
        relaxed[i] = 0;
        not_reached[i] = 0;
    }

    // Ford-Bellman
    vector<long long> d(n, INF);
    d[s] = 0;
    for (int k = 0; k < n - 1; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < vert[i].size(); j++) {
                if (d[vert[i][j].first] > vert[i][j].second + d[i]) {
                    d[vert[i][j].first] = vert[i][j].second + d[i];
                }
            }
        }
    }
    // n-тая итерация
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < vert[i].size(); j++) {
            if (d[vert[i][j].first] > vert[i][j].second + d[i]) {
                relaxed[vert[i][j].first] = 1;
                d[vert[i][j].first] = vert[i][j].second + d[i];
            }
        }
    }

    for (int k = 0; k < n; k++) {
        if (relaxed[k] == 1 && !not_shortest[k]) {
            dfs(k);
        }
    }

    for (int i = 0; i < n; i++) {
        if (d[i] >= INF) {       // >= или == ?
            not_reached[i] = 1;
        }
    }

    for (int i = 0; i < n; i++) {
        if (not_shortest[i]) {
            cout << '-' << '\n';
        }
        else if (not_reached[i]) {
            cout << '*' << '\n';
        }
        else cout << d[i] << '\n';
    }

    return 0;
}