#include <fstream>
#include <vector>
#include <queue>
#include <bitset>

using namespace std;
ifstream f("bellmanford.in.");
ofstream g("bellmanford.out");
const int N = 100010;
const int oo = 2000000010;
int n,m,p,x,y,z,i,d[N];
vector< pair<int,int> > v[N];
queue<int> Q;
bitset<N> q;
int main()
{
    f>>n>>m>>p;
    for (; m; m--)
    {
        f>>x>>y>>z;
        v[x].push_back(make_pair(y,z));
        v[y].push_back(make_pair(x,z));
    }
    fill(d+1,d+n+1,oo);
    d[p]=0;
    Q.push(p);q[p]=1;
    while(Q.size())
    {
        x=Q.front();
        m=d[x];
        for(auto it:v[x])
        {
            y=it.first;
            z=it.second;
            if(m+z<d[y])
            {
                d[y]=m+z;
                if(!q[y])
                {
                    Q.push(y);
                    q[y]=1;
                }
            }
        }
        Q.pop();q[x]=0;
    }
    for(i=1;i<=n;i++)
    {
        if(d[i]==oo)d[i]=-1;
        g<<d[i]<<' ';
    }

    return 0;
}