Tima, Xentopia에 가다

Xentopia 시에는 잘 연결된 철도망이 있다. 시에는 1번부터 N번까지 번호가 붙은 N개의 교차점이 있다. 교차점 사이에 존재하는 M쌍의 철도 선로가 있다. 각 선로에서는 열차가 양방향으로 다닐 수 있다. 각 철도 선로에는 빨강, 파랑, 하양 중 하나의 색이 붙어 있다.

시를 여행하는 관광객 Tima는 교차점 S에서 교차점 T까지 가능한 한 최소 시간에 가고 싶어 한다. 그녀에게는 이 목표를 이루는 데 쓸 수 있는 철도망 지도가 있다.

Tima는 꽤 별나서 여행에 흥미로운 제약을 하나 걸었다. 그녀는 정확히 k1개의 빨간 선로와 정확히 k2개의 파란 선로를 지나고, 하얀 선로는 몇 개든지 임의의 순서로 지나고 싶어 한다. 같은 철도 선로를 여러 번 이용해도 괜찮다.

Tima가 S에서 T까지 가는 데 걸리는 최소 시간을 제약을 어기지 않으면서 구할 수 있는가?

첫째 줄에는 공백으로 구분된 네 정수 N(1 ≤ N ≤ 450), M(1 ≤ M ≤ 1 100), k1, k2가 주어진다(0 ≤ k1, k2 ≤ 800, k1 · k2 ≤ 800). 다음 M개 줄이 이어진다. 각 줄에는 공백으로 구분된 네 정수 U V X C가 주어지며, 이는 교차점 U와 교차점 V 사이에 선로가 있음을 뜻한다(1 ≤ U, V ≤ N, U ≠ V). 열차는 이 선로를 X초에 지나고(0 ≤ X ≤ 109), 선로에는 색 C가 붙어 있다(0 ≤ C ≤ 2). 하얀 선로는 C = 0, 빨간 선로는 C = 1, 파란 선로는 C = 2로 나타낸다.

마지막 줄에는 Tima의 여행의 출발점과 도착점인 S(1 ≤ S ≤ N)와 T(1 ≤ T ≤ N)가 공백으로 구분되어 주어진다. 참고: S는 T와 같을 수 있다.

Tima가 걸리는 총 시간을 나타내는 정수 하나를 출력한다. Tima가 정확히 k1개의 빨간 선로와 k2개의 파란 선로를 지나고 하얀 선로는 몇 개든지 지나서 목적지에 도달하는 것이 불가능하면 -1을 출력한다.