Grandfather told how he walked to school.
Grandfather would leave home and then pass through several transitions between intersections. The intersections are connected by directed streets and directed corridors inside buildings, and movement through these transitions is only allowed in one specific direction. Outside, one can freeze (lose heat), while inside a building, one can warm up (gain heat). Grandfather reached school as quickly as possible, but he never got too cold or too hot on the way, meaning the amount of heat was always within the range of $$$-30$$$ to $$$+30$$$ (inclusive). At the beginning of his journey, Grandfather's heat level was always zero.
Grandfather does not remember the specific path, but he recalls $$$n$$$ intersections numbered from $$$1$$$ to $$$n$$$ that he could traverse, and $$$m$$$ transitions between them. For each transition (which can be either a street or a corridor), Grandfather remembers which intersection it led from and to, how long it took to traverse, and how much heat he lost (in the case of a street) or gained (in the case of a corridor) while passing through it.
Help Grandfather remember the minimum time it took him to get to school, or tell him that he forgot something and that it is impossible to get from home to school without getting too cold or too hot given the specified set of intersections and transitions.
Each test consists of several sets of input data. The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10\,000)$$$ — the number of input data sets. The description of the input data sets follows.
The first line of each input data set contains two integers $$$n$$$, $$$m$$$ $$$(1 \le n, m \le 10^5)$$$ — the number of intersections and the number of transitions between them.
The $$$i$$$-th of the following $$$m$$$ lines contains $$$4$$$ integers $$$u$$$, $$$v$$$, $$$l$$$, and $$$dt$$$ $$$(1 \le u, v \le n, u \ne v$$$, $$$1 \le l \le 10^6$$$, $$$-30 \le dt \le 30)$$$, which indicate the existence of a transition that Grandfather could traverse in time $$$l$$$ from intersection $$$u$$$ to intersection $$$v$$$ with a change in heat of $$$dt$$$ while passing through it. If $$$dt \lt 0$$$, then this transition is a street, and Grandfather lost $$$-dt$$$ heat while passing through it; otherwise, this transition is a corridor in a building, and Grandfather gained $$$dt$$$ heat while passing through it.
Upon leaving home, Grandfather instantly arrived at intersection number $$$1$$$. He instantly entered the school as soon as he reached intersection number $$$n$$$.
It is guaranteed that the sum of $$$n$$$ (and the sum of $$$m$$$) across all input data sets does not exceed $$$10^5$$$.
It is possible that there are multiple transitions from some intersection $$$u$$$ to some intersection $$$v$$$, or that there exists both a transition from $$$u$$$ to $$$v$$$ and a transition from $$$v$$$ to $$$u$$$.
For each test, output a single number — the minimum time it took Grandfather to get from home to school. If it is impossible to reach school without getting too cold or too hot, output $$$-1$$$.
The tests for this problem consist of six groups. Points for each group are awarded only if all tests in the group and all tests in the necessary groups are passed.
| Subtask | Points | Additional Constraints | Necessary Groups | Comments | |
| 0 | 0 | – | – | Tests from the statement. | |
| 1 | 13 | $$$l = 1, dt = 0$$$ | – | – | |
| 2 | 14 | $$$dt = 0$$$ | 1 | – | |
| 3 | 19 | $$$dt | gt; 0$$$ | – | – |
| 4 | 23 | The graph is acyclic$$$^{\dagger}$$$ | – | – | |
| 5 | 31 | – | 1–4 | – |
$$$^{\dagger}$$$ The graph is acyclic, meaning that in subgroup $$$4$$$, it is impossible to reach intersection $$$u$$$ from itself (for any $$$1 \le u \le n$$$) in any non-zero number of transitions. This statement holds true even if the temperature changes on all transitions are considered to be zero.
15 61 2 2 01 4 4 02 3 3 02 5 1 03 2 4 04 5 2 0
3
15 61 2 2 -201 4 4 262 3 3 52 5 1 -153 2 4 104 5 2 27
10
Illustration for the second example. In this example, the shortest path would look like this: $$$1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 5$$$.
Illustration for the second example
