조깅

Pheobe는 운동이 신체와 정신 건강에 큰 영향을 준다는 이야기를 들었다. 그녀는 지금까지 조깅을 해 본 적이 없고, 한번 해 보고 싶어 한다. 하지만 쉽게 지루해하고 같은 일을 반복하기 어려워한다. 조깅을 습관으로 만들기 위해 Pheobe는 도전 과제를 세웠다. 흥미로운 길을 찾을 수 있는 한 매일 저녁 달리러 나가겠다는 것이다. 경로가 흥미롭다는 것은 그 경로가 이전에 달린 적 없는 도로를 지난다는 뜻이다. Pheobe가 계획을 잘 세웠을 때 달릴 수 있는 최대 날짜 수를 구하라.

Pheobe가 사는 동네에 대한 설명이 주어진다. 그녀는 교차로에 살고 있으며, 동네의 모든 교차로를 설명한다. 또한 어떤 교차로가 도로로 연결되어 있는지, 각 도로의 길이(미터)를 알려 준다. 모든 도로는 서로 다른 두 교차로를 잇고, 같은 두 교차로를 잇는 도로가 두 개 이상 있는 경우는 없다. Pheobe가 설명하는 도로는 모두 그녀의 집에서 도달할 수 있으며, 그녀는 걸어서 이동하므로 도로는 양방향으로 지날 수 있다고 가정해도 된다.

유효한 달리기는 Pheobe의 집에서 시작해 집에서 끝나며, 길이는 그녀가 정한 범위 안에 있어야 한다. Pheobe가 도로에 들어설 때 도로 전체를 끝까지 지날 필요는 없다. 어느 지점에서든 되돌아설 수 있으며, 이 경우에도 도로 전체를 본 것으로 취급하여 달리기가 흥미로운지 판단한다. 달리기가 이전 달리기에 나타나지 않았던 도로(또는 그 도로의 일부 구간)를 포함하면 흥미로운 달리기이다. 교차로에 도착했다고 해서 그 교차로에 인접한 도로를 모두 본 것으로 치지는 않는다.

첫 줄에 공백으로 구분된 정수 네 개 $I$ $S$ $L$ $U$가 주어진다. $I$는 교차로의 수이고, $S$는 도로의 수이다. $L$은 유효한 달리기의 최소 길이(미터)이고, $U$는 최대 길이(미터)이다.

이어지는 $S$개의 줄은 각각 도로 하나를 나타내며, 공백으로 구분된 정수 세 개 $i$ $j$ $\ell$이 주어진다. $i$와 $j$는 이 도로가 잇는 교차로이고, $\ell$은 도로의 길이(미터)이다. 교차로는 $0$부터 $I-1$까지 번호가 매겨져 있으며, Pheobe는 교차로 $0$에 산다.

흥미로운 달리기가 연속으로 이어지는 가장 긴 수열의 길이를 나타내는 정수 하나를 한 줄에 출력한다.

• $1 \le I \le 100\,000$
• $0 \le S \le 100\,000$
• $1 \le L \le U \le 42\,195$ (Pheobe는 마라톤 거리보다 더 달리지 않는다)
• $1 \le \ell \le 1\,000$