고속도로

바이트랜드(Byteland)에는 유료 양방향 고속도로가 촘촘하게 깔려 있다. 각 고속도로는 두 도시를 잇는다. 통행료는 날마다 달라지며, 어떤 고속도로를 어느 방향으로 지나는지에 따라 정해진다. 통행료는 하루가 지날 때마다 일정한 양만큼(선형으로) 변한다. 즉 각 고속도로의 각 방향마다 상수 $p$ 가 정해져 있어서, 그 방향의 통행료는 매일 $p$ 만큼 변한다. $p$ 는 음수일 수도(통행료가 줄어듦), $0$ 일 수도(변하지 않음), 양수일 수도(늘어남) 있다. 모든 통행료의 변화는 자정에 일어난다.

바이트가이(ByteGuy)는 도시 $a$ 에 살고, 도시 $b$ 에 사는 친구를 방문하려 한다. 그는 같은 날 안에 $a$ 에서 $b$ 로 갔다가 다시 $b$ 에서 $a$ 로 돌아와야 한다. 알뜰한 그는 고속도로 통행 비용이 가장 적게 드는 날에 이 여행을 하고 싶어 한다. 단, 늦어도 $d$ 번째 날까지는 친구를 방문해야 한다.

바이트랜드의 고속도로망은 매우 잘 발달되어 있어 임의의 두 도시 사이를 오갈 수 있으며, 두 도시를 직접 잇는 고속도로는 최대 하나뿐이다. 바이트랜드는 작은 나라이므로, 가장 싼 경로를 이용하면 하루 안에 $b$ 로 갔다가 집으로 돌아올 수 있다. 처음 $d$ 일 동안 모든 고속도로의 통행료는 항상 양수임이 보장된다.

다음을 수행하는 프로그램을 작성하라.

• 고속도로들의 정보와 바이트가이의 도시 $a$, 친구의 도시 $b$, 날 수 $d$ 를 입력받는다.
• 처음 $d$ 일 중 하루를 골라 $a$ 에서 $b$ 로 갔다가 돌아오는 데 드는 최소 비용을 구한다.
• 그 결과를 표준 출력에 쓴다.

첫 줄에 다섯 정수 $n$, $m$, $a$, $b$, $d$ 가 주어진다 ($2 \le n \le 100\,000$, $1 \le m \le 100\,000$, $2 \le d \le 10\,000$). 여기서 $n$ 은 도시의 수, $m$ 은 고속도로의 수, $a$ 는 바이트가이가 사는 도시, $b$ 는 친구가 사는 도시, $d$ 는 여행을 마쳐야 하는 기한(날 수)이다. 도시는 $1$ 부터 $n$ 까지 번호가 매겨져 있으며, $a$ 와 $b$ 는 서로 다르다.

이어지는 $m$ 개의 줄에 각 고속도로의 정보가 주어진다. 각 줄은 여섯 정수 $n_1$, $n_2$, $c_1$, $p_1$, $c_2$, $p_2$ 로 이루어진다. $n_1$ 과 $n_2$ 는 이 고속도로가 잇는 두 도시이다. $c_1$ 과 $c_2$ 는 각각 첫째 날에 $n_1 \to n_2$, $n_2 \to n_1$ 방향으로 지날 때의 통행료이다. 그 다음 날부터는 매일 첫 번째 통행료가 $p_1$ 만큼, 두 번째 통행료가 $p_2$ 만큼 변한다. 고려하는 기간($1$ 일차부터 $d$ 일차까지) 동안 모든 통행료는 양수이며 $10\,000$ 이하임이 보장된다.

표준 출력에 정수 하나만 출력한다. 이는 처음 $d$ 일 중 하루에 $a$ 에서 $b$ 로 갔다가 돌아오는 데 드는 최소 비용이다.

위 그림에서는 방향별 통행료를 구분해 나타내기 위해, 각 고속도로를 두 개의 방향 간선으로 그렸다. 각 간선 옆의 두 수는 첫째 날의 통행료와 매일 일어나는 통행료의 변화량을 뜻한다.

둘째 날에 $1 \to 2 \to 3 \to 4 \to 1$ 경로를 이용하면 비용은 $23$ 이다.