#1164. 大作业的复仇

在一次数据结构课中，你的作业被选为优秀大作业，获得了上台展示的机会。在上台展示开始之前的一个小时，助教David偷偷告诉你，这节课的代课老师Yang教授安排的上台展示内容竟然是在OJ上现场评测你的代码！更可怕的是，你发现这个评测的要求竟然比你写的作业更高。你感到无比恐慌，并要尽快调整你的代码从而通过上台展示，让Yang教授给你这门课的满分。

有 $n$ 个城市与 $m$ 个单向火车车次，第 $i$ 趟火车会于发车时间 $b_i$ 从起点站 $s_i$ 出发，在到达时间 $e_i$ 到达终点站 $t_i$，中间不停车，票价是 $c_i$。要乘坐这列火车，你必须在 $b_i$ 时刻或 $b_i$ 时刻之前到达这个车站 $s_i$，然后你就会在 $e_i$ 时刻出现在 $t_i$ 车站。由于你是专业卡 deadline 选手，上下车、转车的时间均可以忽略不计，也就是若你在 $t$ 时刻刚刚从某站下车，你仍然可以赶上在这一站 $t$ 时刻出发的列车。

现在是 $0$ 时刻，你正处于 $o$ 车站，你想知道到达各个其他车站的最优方案是什么（你可以转车、在某个车站等待等），可是你需要考虑很多因素：

• 票价 $x$，即方案中乘坐的所有火车的票价之和。
• 乘车次数 $y$，即一共要乘坐几次火车。
• 旅途总用时 $z$，即到达目的地的时刻减去当前的 $0$ 时刻的值。

你想要综合考虑这些因素，因此你选取了三个非负整数 $A,B,C$，定义方案的“代价”为 $Ax+By+Cz$。你想知道对每个城市，到达这个城市的方案“代价”的最小值是多少。如果无法到达某个城市，请在相应位置输出 $-1$。

第一行三个正整数 $n,m,o$ 表示城市数、火车路线数和你目前所在的城市。（$1\leq n,m\leq 5\times 10^5, 1\leq o \leq n$）

第二行三个非负整数 $A,B,C$ ，意义如题目描述中所示。（$0\leq A,B,C\leq 10^3$）

接下来 $m$ 行描述火车车次，每行五个整数 $s,t,b,e,c$ （$1\leq s,t\leq n, 0\leq b<e\leq 10^6, 0\leq c\leq 10^9$），表示路线的起点站城市编号、终点站城市编号、出发时间、到达时间与票价。

共 $n$ 行，第 $i$ 行一个整数表示从城市 $p$ 到城市 $i$ 最优方案的“代价”，如果无法到达城市 $i$，则这一行是 $-1$。

样例输入1

5 7 4
1 0 0
2 3 9 11 1
1 2 0 1 3
5 1 3 5 1
3 4 12 15 1
4 5 0 2 1000
5 3 3 4 1000
1 2 6 8 1

样例输出1

1001
1002
1003
0
1000

样例输入2

5 7 4
0 1 0
2 3 9 11 1
1 2 0 1 3
5 1 3 5 1
3 4 12 15 1
4 5 0 2 1000
5 3 3 4 1000
1 2 6 8 1

样例输出2

2
3
2
0
1

样例输入3

5 7 4
0 0 1
2 3 9 11 1
1 2 0 1 3
5 1 3 5 1
3 4 12 15 1
4 5 0 2 1000
5 3 3 4 1000
1 2 6 8 1

样例输出3

5
8
4
0
2

样例输入4

5 7 1
2 3 3
2 3 9 11 1
1 2 0 1 3
5 1 3 5 1
3 4 12 15 1
4 5 0 2 1000
5 3 3 4 1000
1 2 6 8 1

样例输出4

0
12
43
60
-1

样例解释

以上四个样例对应的都是如下的交通图，只是起点站和优化策略不同。（路线上的 # 后的数字表示边的编号，a:b 表示 a 时刻出发，b 时刻到达，￥后的数字表示票价）

输入较大，请使用较快的输入输出方式（如 scanf，关同步后的 cin 等）。如有需要，下面提供一个快速输入/输出模板供参考。（但此题目时间限制已是没用快速输入输出标程的 3 倍）

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<typename T> void read(T &x){
    x = 0; int f = 1; char ch = gc();
    while(!isdigit(ch) ) { if(ch == '-') f = -1; ch = gc();}
    while( isdigit(ch) ) {x = x * 10 + ch - 48; ch = gc();}
    x *= f;
}
template<typename T, typename... Args> void read(T& x, Args&... args)
{ read(x), read(args...); }
template<typename T> void write(T x) {
    if(x < 0) { putchar('-'), write(-x); return; }
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

最好采用线性算法。