#include <fstream>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct graf
{
    int nod,cost;
    graf *leg;
};
graf *G[10001];
int n,start;
bool viz[10001];
int coada[10001],d[10001],t[101];

void add(int x,int y,int q)
{
    graf *p=new graf;
    p->nod=y;
    p->cost=q;
    p->leg=G[x];
    G[x]=p;

}
void bellman()
{
    int inc=1,sf=1;
    int i;
    for(i=1;i<=n;i++)
        d[i]=100001;
    d[start]=0;
    coada[1]=start;
    viz[start]=true;
    bool ciclu=false;
    t[start]=1;
    while(inc<=sf and !ciclu)
    {
        for(graf *p=G[coada[inc]];p;p=p->leg)
            if(d[p->nod]>d[coada[inc]]+p->cost)
        {
            t[p->nod]++;
            d[p->nod]=d[coada[inc]]+p->cost;
            if(!viz[p->nod])
            {
                coada[++sf]=p->nod;
                viz[p->nod]=true;
            }
        }
        viz[coada[inc]]=false;
        if(t[coada[inc]]>=n)
            ciclu=true;
        inc++;
    }
}
int main()
{
    int x,y,q;
    f>>n>>start;
    while(f>>x)
    {
        f>>y>>q;
        add(x,y,q);
    }
    bellman();
    for(int i=1;i<=n;i++)
        if(d[i]==100001)
            g<<"-1 ";
        else g<<d[i]<<' ';
    return 0;
}