Playground Hideout

Little Timmy loves playgrounds, especially ones with elaborate wooden towers linked by plank bridges and ropes, with slides and rope-ladders. He would play on his favourite playground for days if his parents let him, but sooner or later they decide it is time to go home. For their next trip Timmy has a plan: instead of letting his father simply grab him, he will climb to the highest platform of the most complex structure and hide there, buying himself some extra time.

An adventure playground consists of several platforms. The difficulty of reaching a platform directly from ground level varies from platform to platform. Platforms are also interconnected by bridges of varying difficulty, and some connections (such as slides) are far easier to use in one direction than in the other.

Given a plan of an adventure playground, help Timmy find the platform that is hardest to reach from ground level. The difficulty of a path is the sum of the difficulties of the connections it uses, and the difficulty of reaching a platform is the difficulty of the least difficult path from ground level to that platform.

The first line contains a single integer $n$, the number of test cases.

Each test case begins with a line containing two integers $p$ and $c$ ($1 \le p, c \le 10000$), the number of platforms and connections respectively. The next line contains $p$ integers; the $i$-th of them, $d_i$ ($0 \le d_i \le 1000$), is the difficulty of reaching platform $i$ directly from ground level.

Each of the following $c$ lines describes one connection with four integers $i$, $j$, $a$, $b$ ($i < j$), where $i$ and $j$ are the zero-based indices of the two connected platforms, $a$ ($0 \le a \le 1000$) is the difficulty of going from platform $i$ to platform $j$, and $b$ ($0 \le b \le 1000$) is the difficulty of going from platform $j$ to platform $i$. There may be multiple connections between the same pair of platforms.

For each test case, first print a line Scenario #i:, where $i$ is the number of the test case, counting from 1. Then print a single line containing the zero-based index of the platform that is hardest to reach from ground level. If several platforms are equally hard to reach, print the smallest such index. Separate consecutive test cases with a blank line.