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개의 정수 선택 방법이 몇 가지인지 구하는 프로그램을 작성하세요.

#8058 upload - done - how_to_reg - call_split Subtask

건설사업 2 timer 1s memory 1024MB

#8058
Subtask

건설사업 2 1s 1024MB