Two Roads

Ulsan has $N$ intersections numbered from $1$ to $N$, and $M$ roads connecting them. Each road is one-way, and the time needed to travel along it is fixed. Yoon drives every day from home to the office in a car with Hyundai Mobis's self-driving system. Yoon's home is at intersection $S$, and the office is at intersection $T$. The self-driving system always uses a route that takes the shortest time from home to the office. Yoon recently heard that two new roads will be built in Ulsan. Yoon expects to reach the office faster, but Yoon does not know which intersections the new roads connect or how long they take. So Yoon assumes $Q$ road construction scenarios and wants to calculate the route the car would take in each case. For each scenario, find the time Yoon needs to drive from home to the office using the self-driving system.

The first line contains the number of intersections $N$, the number of existing roads $M$, the home intersection $S$, and the office intersection $T$, separated by spaces. ($2\leq N\leq 300$; $0\leq M\leq 3\ 000$; $1\leq S,T\leq N$; $S\neq T$)

The next $M$ lines each contain three integers $u$, $v$, $w$ separated by spaces. They describe a one-way road from intersection $u$ to intersection $v$ that takes $w$ time to traverse. ($1\leq u,v\leq N$; $1\leq w\leq 10^6$)

The next line contains the number of construction scenarios $Q$. ($1\leq Q\leq 100\ 000$)

The next $Q$ lines each contain six integers $a_1$, $b_1$, $c_1$, $a_2$, $b_2$, $c_2$ separated by spaces. They describe a scenario in which two new one-way roads are built: one from intersection $a_1$ to $b_1$ taking $c_1$ time, and one from intersection $a_2$ to $b_2$ taking $c_2$ time. ($1\leq a_1,b_1,a_2,b_2\leq N$; $1\leq c_1,c_2\leq 10^6$)

The same pair of intersections may be connected by several roads, and a road may start and end at the same intersection.

For each construction scenario, print on its own line the time Yoon needs to drive from home to the office. If the trip is impossible in a scenario, print $-1$ on that line.