//#include <iostream>
#include <fstream>
#include <queue>

using namespace std;
int n,m,x,y;
int a,b,c,p,i,v;
int d[30001];
vector<pair<int,int>>g[30001];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> >>q;

ifstream cin("sate.in");
ofstream cout("sate.out");

void dijkstra()
{
    for (i=1;i<=n;i++) d[i]=(1<<30);
    d[x]=0;
    q.push(make_pair(0,x));
    while (q.size()>0)
    {
        p=q.top().second;
        cout<<p<<" ";
        for (auto a:g[p])
        {
            v=a.first;  //  vecin
            c=a.second;  //  cost
            if (d[v]>d[p]+c)
            {
                d[v]=d[p]+c;
                q.push(make_pair(d[v],v));
            }
        }
        q.pop();
    }
}

int main()
{
    cin>>n>>m>>x>>y;
    for (i=1;i<=m;i++)
    {
        cin>>a>>b>>c;
        g[a].push_back(make_pair(b,c));
        g[b].push_back(make_pair(a,-c));
    }
    dijkstra();
    cout<<"\n";
    for (i=1;i<=n;i++) cout<<d[i]<<" ";
}