문제
JOI 국가에는 N개의 역이 있으며, 이들 역에는 1부터 N까지 번호가 매겨져 있습니다. 또한 JOI 국가에는 M개의 철도 노선이 있으며, 이들 노선에는 1부터 M까지 번호가 매겨져 있습니다. 철도 노선 i (1 ≦ i ≦ M)는 역 Ai와 역 Bi를 양방향으로 연결하며, 그 이동에는 Ci 분이 소요됩니다.
JOI 국가의 장관인 당신은 아래와 같이 새로운 철도 노선 1개를 건설하기로 결정했습니다.
1 ≦ u < v ≦ N을 만족하는 정수 u, v를 선택합니다. 역 u와 역 v를 양방향으로 연결하며, 그 이동에는 L 분이 소요되는 철도 노선을 JOI 국가에 건설합니다. 이미 역 u와 역 v를 양방향으로 연결하는 철도 노선이 있어도 상관없습니다.
당신이 건설을 마친 후, 역 S에서 역 T까지 몇 개의 철도 노선을 사용하여 K 분 이내에 이동할 수 있게 되면 국왕이 기뻐할 것입니다. 이때, 철도 노선의 환승 시간이나 대기 시간은 고려하지 않기로 합니다.
건설할 때 2개의 정수 u, v를 선택하는 방법은 N(N-1)/2 가지가 있지만, 이 중에서 국왕이 기뻐할 만한 선택 방법이 몇 가지인지 알고 싶습니다.
역과 철도 노선, 국왕의 요구 사항 정보가 주어졌을 때, 국왕이 기뻐할 만한 2개의 정수 선택 방법이 몇 가지인지 구하는 프로그램을 작성하세요.
입력
입력은 아래와 같은 형식으로 표준 입력으로 주어집니다.
N M
S T L K
A1 B1 C1
A2 B2 C2
.
.
.
AM BM CM
[제약 조건]
2 ≦ N ≦ 200,000
1 ≦ M ≦ 200,000
1 ≦ S < T ≦ N
1 ≦ L ≦ 10^9
1 ≦ K ≦ 10^15
1 ≦ Ai < Bi ≦ N (1 ≦ i ≦ M)
(Ai, Bi), (Aj, Bj) (1 ≦ i < j ≦ M)
1 ≦ Ci ≦ 10^9 (1 ≦ i ≦ M)
입력되는 값은 모두 정수입니다.
출력
표준 출력으로, 국왕이 기뻐할 만한 2개의 정수 선택 방법이 몇 가지인지 1행으로 출력하세요.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 8점 | L = 1, K = 2, Ci = 1 (1 ≦ i ≦ M) |
| #2 | 16점 | N ≦ 50, M ≦ 50 |
| #3 | 29점 | N ≦ 3,000, M ≦ 3,000 |
| #4 | 47점 | 추가 제약 조건 없음 |
예제1
78
6712
121
161
231
241
351
371
451
561
4
예를 들어, u = 3, v = 6을 선택했다고 가정합니다. 역 3과 역 6을 양방향으로 연결하고, 그 이동에 1분이 소요되는 철도 노선을 JOI 국가에 건설합니다.
이때, 다음과 같이 역 6에서 역 7까지 철도 노선을 사용하여 2분 만에 이동할 수 있습니다. 역 6에서 역 7까지 2분 이내에 이동할 수 있으므로, 국왕이 기뻐할 것입니다.
역 3과 역 6을 양방향으로 연결하는 노선을 사용하여 역 6에서 역 3으로 이동합니다. 이때 1분이 소요됩니다.
역 3과 역 7을 양방향으로 연결하는 노선을 사용하여 역 3에서 역 7로 이동합니다. 이때 1분이 소요됩니다.
국왕이 기뻐할 만한 2개의 정수 선택 방법은 이 경우를 포함하여 4가지가 있습니다. 따라서 4를 출력합니다.
이 입력 예시는 소과제 1, 2, 3, 4의 제약 조건을 만족합니다.
예제2
32
1312
121
231
3
어떤 2개의 정수를 선택해도 국왕은 기뻐할 것입니다. 즉, 국왕이 기뻐할 만한 2개의 정수 선택 방법은 3가지가 있습니다. 따라서 3을 출력합니다.
이 입력 예시는 소과제 1, 2, 3, 4의 제약 조건을 만족합니다.
예제3
1821
486787307723000000062
513805281073
81780983648
38996533440
1016514277428
2557914340
611966149890
812532734310
29188599710
23966306014
1216656457780
1618662633078
115698078877
28665665772
26652261981
1415712798281
713571169114
1314860543313
67454251187
914293590683
614959532841
311591245645
16
이 입력 예시는 소과제 2, 3, 4의 제약 조건을 만족합니다.