题目描述

顺利通过了黄药师的考验，下面就可以尽情游览桃花岛了！

你要从桃花岛的西头开始一直玩到东头，然后在东头的码头离开。可是当你游玩了一次后，发现桃花岛的景色实在是非常的美丽！！！于是你还想乘船从桃花岛东头的码头回到西头，再玩一遍，但是桃花岛有个规矩：你可以游览无数遍，但是每次游玩的路线不能完全一样。

我们把桃花岛抽象成了一个图，共 $n$ 个点代表路的相交处，$m$ 条边表示路，边是有向的（只能按照边的方向行走），且可能有连接相同两点的边。输入保证这个图没有环，而且从西头到东头至少存在一条路线。两条路线被认为是不同的当且仅当它们所经过的路不完全相同。

你的任务是：把所有不同的路线游览完一共要花多少时间？

输入格式

第一行为 $5$ 个整数 $n,m,s,t_0,t_1$，分别表示点数，边数，岛西头的编号，岛东头的编号（编号是从 $1$ 到 $n$）和你乘船从岛东头到西头一次的时间。

以下 $m$ 行，每行 $3$ 个整数 $x,y,t$，表示从点 $x$ 到点 $y$ 有一条行走耗时为 $t$ 的路。

每一行的多个数据之间用一个空格隔开。

输出格式

假设总耗时为 $total$，则输出 $total\ \bmod 10000$ 的值（$total$ 对 $10000$ 取余）。

3 4 1 3 7
1 2 5
2 3 7
2 3 10
1 3 15

56

说明 / 提示

【样例说明】

共有 $3$ 条路径可以从点 $1$ 到点 $3$，分别是 $1-2-3$，$1-2-3$，$1-3$。

时间计算为：

$(5+7)+7 +(5+10)+7 +(15)=56$

22 45 1 22 340
1 2 539
2 3 954
3 4 848
4 5 963
5 6 615
6 7 651
7 8 515
8 9 330
9 10 516
10 11 711
11 12 22
12 13 273
13 14 709
14 15 106
15 16 280
16 17 26
17 18 346
18 19 579
19 20 122
20 21 84
21 22 373
17 19 356
14 22 181
12 17 857
4 10 477
3 21 763
4 9 159
19 21 345
4 8 237
3 15 292
6 10 42
11 15 366
13 16 770
10 22 859
18 21 531
9 21 216
5 12 280
3 22 422
9 12 339
7 19 105
13 17 859
20 22 804
14 17 385
12 14 681
10 21 145

998

42 90 1 42 9146
1 2 539
2 3 44
3 4 533
4 5 1000
5 6 281
6 7 398
7 8 946
8 9 246
9 10 25
10 11 768
11 12 476
12 13 958
13 14 686
14 15 58
15 16 509
16 17 492
17 18 499
18 19 595
19 20 421
20 21 971
21 22 63
22 23 326
23 24 950
24 25 427
25 26 763
26 27 317
27 28 781
28 29 314
29 30 308
30 31 474
31 32 753
32 33 442
33 34 440
34 35 718
35 36 301
36 37 685
37 38 40
38 39 54
39 40 58
40 41 25
41 42 175
10 34 764
35 42 599
20 33 54
37 41 454
29 40 541
29 31 893
16 36 608
18 23 176
26 35 357
2 10 708
38 40 554
2 20 747
38 41 218
24 40 560
17 20 308
3 33 991
29 42 355
14 17 518
11 16 500
29 39 986
19 42 893
1 18 800
40 42 252
30 39 382
15 29 619
8 27 724
35 38 633
15 34 989
16 37 45
5 37 396
23 41 866
5 10 788
10 18 66
18 36 100
38 42 938
24 30 255
35 37 283
8 39 923
18 29 330
30 33 194
25 35 221
33 37 622
21 38 505
33 39 891
9 36 298
23 30 453
27 31 821
28 39 739
6 21 699

3084

数据范围

$2\leq n\leq 10^4$，$1\leq m\leq 5\times 10^4$，$t_0\leq 10^4$，$t_1\leq 10^4$。