#include <fstream>
#define DMAX 1000
#define INFINIT 1000
using namespace std;

ifstream fin("bellman_ford.in");
ofstream fout("bellman_ford.out");

int n, m, vf_start;
int tata[DMAX];
int Cmin[DMAX];
int C[DMAX][DMAX];
short int M[DMAX];

void citire();
void init();
void dijkstra();
void bellman_ford();
void afisare();

int main()
{
    citire();
    init();
    //dijkstra();
    bellman_ford();
    afisare();
    return 0;
}

void citire()
{
    fin >> n >> m >> vf_start;


    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            C[i][j] = INFINIT;
            C[i][i] = 0;
        }
    }

    int i,x,y,c;
    for(i = 1; i <= m; i++)
    {
        fin >> x >> y >> c;
        C[x][y] = c;
    }

    fin.close();
}

void init()
{
    M[vf_start] = 1;
    int i;
    for(i = 1; i <= n; i++)
    {
        Cmin[i] = C[vf_start][i];
        tata[i] = vf_start;
    }
    tata[vf_start] = 0;
}

int minim()
{
    int res = 0, vfmin = 0;
    int i = 1;

    for(i = 1; i <= n; i++)
    {
        if(M[i] == 0 )
        {
            res = Cmin[i];
            vfmin = i;
            break;
        }
    }

    for(i; i <= n; i++)
    {
        if(Cmin[i] < res && M[i] == 0 )
        {
            res = Cmin[i];
            vfmin = i;
        }
    }

    M[vfmin] = 1;

    return vfmin;
}

void dijkstra()
{
    int i, x, vfmin;
    for(i = 1; i <= n-1; i++)
    {
        vfmin = minim();

        for(x = 1; x <= n; x++)
        {
            if(M[x] == 0 && Cmin[x] > Cmin[vfmin] + C[vfmin][x])
            {
                Cmin[x] = Cmin[vfmin] + C[vfmin][x];
                tata[x] = vfmin;
            }
        }
    }
}

void afisare()
{
    int i;
    for(i = 1; i <= n; i++)
    {
        fout <<  Cmin[i] <<' ';
    }

    fout.close();
}

void bellman_ford()
{
    int i, x,y,op;
    for(i = 1; i <= n; i++)
    {
        op=0;
        for(x = 1; x <= n; x++)
        {
            for(y=1;y<=n;y++)
                if( Cmin[y] > Cmin[x] + C[x][y])
                {
                    Cmin[y] = Cmin[x] + C[x][y];
                    tata[y] = x;
                    op=1;
                }
        }
    }
    if(op)
        {fout<<"ciclu negativ"; fout.close();}
    else
        afisare();
}