두 도로

울산에는 $1$번부터 $N$번까지 번호가 붙은 $N$개의 교차로가 있고, 교차로와 교차로를 잇는 $M$개의 도로가 있다. 각 도로는 일방통행이며, 도로를 따라 이동하는 데 걸리는 시간이 정해져 있다.

윤이는 매일 현대모비스의 자율주행 시스템을 탑재한 차를 타고 집에서 회사로 출근한다. 윤이의 집은 $S$번 교차로에, 회사는 $T$번 교차로에 있다. 현대모비스의 자율주행 시스템은 항상 집에서 회사까지 최단 시간이 걸리는 주행 경로를 이용한다.

윤이는 얼마 전 울산에 새로운 도로 두 개가 건설될 것이라는 계획을 들었다. 윤이는 앞으로 회사에 더 빠르게 출근할 수 있을 거라는 기대감에 부풀어 있다. 하지만 윤이는 새 도로가 어떤 교차로를 잇는지와, 새 도로를 따라 이동하는 데 걸리는 시간이 얼마인지에 대한 내용을 듣지는 못했다. 따라서 윤이는 $Q$개의 도로 건설 시나리오를 가정하고, 각 상황에서 윤이의 자율주행차가 어떤 경로를 따라 주행할지 계산해 보기로 했다.

윤이가 가정한 $Q$개의 도로 건설 시나리오 각각에 대해, 윤이가 현대모비스 자율주행 시스템을 이용하여 집에서 회사로 출근하는 데 걸리는 시간을 구하시오.

첫 번째 줄에 교차로의 수 $N$, 기존 도로의 수 $M$, 집의 교차로 번호 $S$, 회사의 교차로 번호 $T$가 공백으로 구분되어 주어진다. ($2\leq N\leq 300$; $0\leq M\leq 3\ 000$; $1\leq S,T\leq N$; $S\neq T$)

이후 $M$개의 줄에 기존 도로에 대한 정보를 나타내는 정수 $u$, $v$, $w$가 공백으로 구분되어 주어진다. 시작 교차로가 $u$번, 도착 교차로가 $v$번이고 이동하는 데 $w$의 시간이 걸리는 일방통행 도로를 나타낸다. ($1\leq u,v\leq N$; $1\leq w\leq 10^6$)

그 다음 줄에 도로 건설 시나리오의 수 $Q$가 주어진다. ($1\leq Q\leq 100\ 000$)

이후 $Q$개의 줄에 새로 건설될 두 개의 도로에 대한 정보를 나타내는 정수 $a\_1$, $b\_1$, $c\_1$, $a\_2$, $b\_2$, $c\_2$가 공백으로 구분되어 주어진다. 시작 교차로가 $a\_1$번, 도착 교차로가 $b\_1$번이고 이동하는 데 $c\_1$의 시간이 걸리는 일방통행 도로와, 시작 교차로가 $a\_2$번, 도착 교차로가 $b\_2$번이고 이동하는 데 $c\_2$의 시간이 걸리는 일방통행 도로를 새롭게 건설하는 시나리오를 나타낸다. ($1\leq a\_1,b\_1,a\_2,b\_2\leq N$; $1\le c\_1,c\_2\le 10^6$)

같은 교차로 쌍을 잇는 도로가 여러 개 주어질 수 있으며, 시작 교차로와 도착 교차로가 동일한 도로가 주어질 수 있다.

각 도로 건설 시나리오에 대해, 윤이가 집에서 회사로 출근하는 데 걸리는 시간을 $Q$개의 줄에 걸쳐 출력한다. 만약 어떤 시나리오에서 집에서 회사로 출근하는 것이 불가능하다면, 해당 줄에는 대신 $-1$을 출력한다.