#include <fstream>
#define INF 999999
using namespace std;

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


int n, mc, st, c[101][101], cmin[101], tata[101], m[101], vfmin;
int changes;

void citire();
void bellman();
void afisare();

int main()
{
    citire();
    bellman();
    afisare();
    return 0;
}

void citire()
{
    int i, j, x, y, co;
    fin >> n >> mc >> st;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            c[i][j]=INF;
    for(i=1;i<=n;i++)
        c[i][i]=0;
    for(i=1;i<=mc;i++)
    {
        fin >> x >> y >> co;
        c[x][y]=co;
    }
}

void bellman()
{
    int i, j, k;
    for(i=1;i<=n;i++)
        cmin[i]=INF;
    cmin[st]=0;
    for(k=1;k<=n;k++)
    {
        changes=0;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                if(cmin[i]!=INF && c[i][j]!=INF)
                    if(cmin[j]>cmin[i]+c[i][j])
                    {
                        cmin[j]=cmin[i]+c[i][j];
                        changes=1;
                    }
            }
    }
}

void afisare()
{
    int i;
    if(!changes)
        for(i=1;i<=n;i++)
            fout << cmin[i] << ' ';
    else
        fout << "NO SOLUTION FOUND!";
}