Volunteering

Limits: 4 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Zenyk has recently been actively volunteering, delivering necessary supplies to the Armed Forces of Ukraine on the frontline. For this, he has to travel extensively across Ukraine, coming under constant shelling by the Russians.

Ukraine can be represented as a set of \(n\) cities and \(m\) bidirectional roads between some pairs of cities. Zenyk needs \(l_i\) minutes to travel along road \(i\). The Russians constantly shell each of the \(m\) roads with a certain periodicity. Road \(i\) is shelled by the Russians for \(c_i\) minutes, then they load new shells for \(d_i\) minutes and shell it again for \(c_i\) minutes, load shells for \(d_i\) minutes again, shell it again, and so on. At the moment of shelling, it is too dangerous to travel on the road. That is, at time intervals \((0, c_i)\), \((c_i + d_i, 2 c_i + d_i)\), \((2 c_i + 2 d_i, 3 c_i + 2 d_i)\) and so on, it is impossible to travel on road \(i\), while at times \([c_i, c_i + d_i], [2 c_i, 2 c_i + 2 d_i], [3 c_i, 3 c_i + 3 d_i]\) and so on, it is possible.

Zenyk starts his journey at time moment 0 and needs to deliver aid to the Armed Forces from the city numbered \(1\) to the city numbered \(n\). What is the minimum time required for this?

Input

The first line contains two numbers \(n\) and \(m\) — the number of cities and the number of roads between them, respectively.

The next \(m\) lines each contain 5 numbers separated by spaces \(u_i\), \(v_i\), \(l_i\), \(c_i\), \(d_i\), where \(u_i\) and \(v_i\) are the numbers of the cities connected by road \(i\). Here \(l_i\) is the number of minutes to travel this road, \(c_i\) and \(d_i\) are numbers from the problem statement that determine the periodicity of the shelling of this road by the Russians.

Output

Output a single number — the minimum time moment in minutes when Zenyk can deliver aid from city 1 to city \(n\).

If the delivery fails due to too intense shelling by the Russians, output Try again the next day!.

Constraints

\(1 \le u_i, v_i \le n\),

\(1 \le l_i, c_i, d_i \le 1000\),

10 points:

\(1 \le n \le 1000\),

\(1 \le m \le 3000\),

15 points:

\(1 \le n \le 15 \cdot 10^4\),

\(1 \le m \le 3 \cdot 10^5\).

Samples

Input (stdin) сopy	Output (stdout) сopy
3 2 1 2 4 4 7 2 3 4 7 4	22

Input (stdin) сopy	Output (stdout) сopy
2 1 1 2 5 7 4	Try again the next day!

Notes

In the first test, at time moment 0, the Russians start shelling both roads. Zenyk stays in the first city until the shelling of the first road ends and rides along it for 4 minutes to city 2, arriving at the city at time moment 8. Zenyk arrives at city 2 and realizes that although the Russians are not currently shelling the road to city 3, he will not manage to arrive there before time moment 11 when the Russians start shelling again. Therefore, Zenyk waits until time moment 18 when the Russians finish the second shelling of road 2 and then rides along it for 4 minutes to city 3, arriving at the city at time moment 22.

In the second test, the time intervals for riding the road last 4 minutes, while the road itself takes 5 kilometers (units of length/time), so Zenyk will not be able to travel along the road and Try again the next day! should be output.