#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

class LN{
private:
    const static long long base = 1000000000000000;
    const static int size = 2;

    bool cmp(const LN& a)const{
        int k = size - 1;
        while (k >= 0 && a.d[k] == 0 && d[k] == 0) k--;
        if (k == -1) return false;
        return d[k] < a.d[k];
    }

public:
    LN(){
        sign = 0;
        for (int i = 0; i < size; i++)
            d[i] = 0;
    }
    LN(long long x){
        if (x < 0){
            sign = 1;
            x = -x;
        }
        else sign = 0;

        for (int i = 0; i < size; i++)
            d[i] = 0;
        d[0] = x % base;
        d[1] = x / base;
    }
    LN(const LN& x){
        sign = x.sign;
        for (int i = 0; i < size; i++)
            d[i] = x.d[i];
    }
    LN operator + (const LN& a) const{
        LN c;
        if (sign == a.sign){
            c.sign = sign;
            for (long long i = 0, s = 0; i < size; i++){
                c.d[i] = d[i] + a.d[i] + s;
                s = c.d[i] / base;
                c.d[i] = c.d[i] % base;
            }
        }
        else{
            bool f = cmp(a);
            if (f)
                c.sign = a.sign;
            else
                c.sign = sign;
            if (!f)
                for (long long i = 0, s = 0; i < size; i++){
                    c.d[i] = d[i] - a.d[i] - s;
                    s = 0;
                    while (c.d[i] < 0){
                        c.d[i] += base;
                        s++;
                    }
                }
            else
                for (long long i = 0, s = 0; i < size; i++){
                    c.d[i] = a.d[i] - d[i] - s;
                    s = 0;
                    while (c.d[i] < 0){
                        c.d[i] += base;
                        s++;
                    }
                }
        }
        return c;
    }
    bool operator == (const LN& a)const {
        int k = size - 1;
        while (k >= 0 && a.d[k] == 0 && d[k] == 0) k--;
        if (k == -1) return true;
        if (sign != a.sign)
            return false;
        while (k >= 0){
            if (d[k] != a.d[k]) return false;
            k--;
        }
        return true;
    }
    bool operator < (const LN& a)const {
        if ((*this) == a) return false;
        if (sign != a.sign){
            if (sign == 1) return true;
            else return false;
        }
        bool f = cmp(a);
        if (sign == 1)
            return !f;
        else
            return f;
    }
    void print(){
        int k = size - 1;
        while (k >= 0 && d[k] == 0) k--;
        if (k == -1){
            cout << 0 << endl;
            return;
        }
        if (sign) cout << '-';
        printf("%lld", d[k]);
        k--;
        while (k >= 0){
            printf("%09lld", d[k]);
            k--;
        }
        cout << endl;
    }

    static LN getINF(){
        LN c;
        for (int i = 0; i < size; i++)
            c.d[i] = base - 1;
        return c;
    }

    int sign;
    long long d[size];
};

LN INF = LN::getINF();

int n, m, s;
struct edge{
    int from, to;
    LN w;
};

edge g[10000];

int main(){
    cin >> n >> m >> s;
    s--;
    for (int i = 0; i < m; i++){
        long long x, y, w;
        cin >> x >> y >> w;
        x--, y--,
        g[i].from = x;
        g[i].to = y;
        g[i].w = LN(w);
    }
    random_shuffle(g, g + m);

    LN dist[10000], dist2[10000];
    for (int i = 0; i < n; i++)
        dist[i] = INF;
    dist[s] = 0;

    for (int k = 0; k < n; k++)
        for (int i = 0; i < m; i++)
            if (dist[g[i].from] < INF)
                dist[g[i].to] = min(dist[g[i].to], dist[g[i].from] + g[i].w);

    for (int i = 0; i < n; i++)
        dist2[i] = LN(dist[i]);

    for (int k = 0; k < n; k++)
        for (int i = 0; i < m; i++)
            if (dist[g[i].from] < INF)
                dist[g[i].to] = min(dist[g[i].to], dist[g[i].from] + g[i].w);

    for (int i = 0; i < n; i++)
        if (dist[i] == INF)
            cout << "*\n";
        else if (dist[i] < dist2[i])
            cout << "-\n";
        else
            dist[i].print();


    return 0;
}