TNFSHOJ 565

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define SZ(X) (int)(X).size()

int n,m,a,b,s;
vector<int> edges[100001];
vector<int> weight[100001];
int ans[100001];
bool vis[100001];

struct state{
    int u, cost;
    bool operator>(const state &rhs)const{
        return cost > rhs.cost;
    }
};

int32_t main(){
    cin >> n >> m >> a >> b >> s;
    for(int i = 0; i < m; ++i){
        int u,v,w;
        cin >> u >> v >> w;
        edges[u].emplace_back(v);
        edges[v].emplace_back(u);
        weight[u].emplace_back(a+b*w);
        weight[v].emplace_back(a+b*w);
    }
    priority_queue<state, vector<state>, greater<state> > pq;
    state ori = {.u = s, .cost = 0};
    pq.push(ori);
    while(!pq.empty()){
        state tmd = pq.top();
        pq.pop();
        if(vis[tmd.u])continue;
        vis[tmd.u] = 1;
        ans[tmd.u] = tmd.cost;
        for(int i = 0; i < SZ(edges[tmd.u]); ++i){
            state nxt;
            nxt.u = edges[tmd.u][i];
            if(vis[nxt.u])continue;
            nxt.cost = tmd.cost + weight[tmd.u][i];
            pq.push(nxt);
        }
    }
    for(int i = 1; i <= n; ++i){
        cout << ans[i] << ' ';
    }
    cout << '\n';
    return 0;
}