Back Before You Left

A strange town has n squares, numbered 0 to n - 1. roads lists two-way roads [a, b, minutes]: walking between squares a and b, in either direction, takes minutes minutes. tunnels lists one-way time tunnels [a, b, minutes]: stepping in at square a brings you out at square b at a moment minutes minutes before the moment you stepped in.

Write back_in_time(n, roads, tunnels) that returns True if there is a square from which you can travel along roads and tunnels and arrive back at that same square at an earlier moment than when you left it, and False otherwise.

Examples

back_in_time(3, [[0, 1, 3], [1, 2, 4]], [[2, 0, 8]])  # returns True
back_in_time(3, [[0, 1, 3], [1, 2, 4]], [[2, 0, 7]])  # returns False
back_in_time(2, [[0, 1, 5]], [[0, 1, 6]])  # returns True

In the first town, walking from square 0 to square 2 takes 3 + 4 = 7 minutes, and the tunnel from square 2 to square 0 goes back 8, so you are home 1 minute before you left. In the second town you arrive at the exact moment you left, which does not count. In the third, the tunnel takes you to square 1 six minutes back in time, and walking home takes only 5.

Constraints

• 1 <= n <= 300, with up to 2,000 roads and 300 tunnels.
• minutes is an integer from 0 to 10,000. A road or tunnel may start and end at the same square, and two squares can be joined by several roads and tunnels.