#include <iostream>
#include <fstream>
#define oo 9999999999
using namespace std;

ifstream fin("graf.in");
ofstream fout("graf.out");
int graf[100][100];
    int d[100],v[100];
    int k,s,n,m,i,j,x,y,c;
    int nodcostmin;
int main()
{


    fin>>n>>m;

    for(i=0;i<=n;i++)
    {
        for(j=0;j<=n;j++)
        {
            graf[i][j]==oo;
        }
    }
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;

        graf[x][y]=c;
    }

    fin>>s;

    for(i=1;i<=n;i++)
    {
        v[i]=0;
        d[i]=graf[s][i];
    }

    v[s]=1;
    d[s]=0;
    d[0]=oo;

    for(k=1;k<=n;k++)
    {
        nodcostmin=0;

        for(i=1;i<=n;i++)
        {
            if(v[i]==0 && d[i]<d[nodcostmin])
                nodcostmin=i;
        }

        if(nodcostmin>-1)
        {
            v[nodcostmin]=1;

            for(i=1;i<=n;i++)
            {
                if(v[i]==0 && d[i]>d[nodcostmin]+graf[nodcostmin][i])
                    d[i]=d[nodcostmin]+graf[nodcostmin][i];
            }
        }
    }

    for(i=1;i<=n;i++)
    {
        fout<<d[i]<<' ';
    }

    return 0;
}