It is your first day on the job — and your first commute! You are eager to get to the office quickly and start coding, trading, or doing whatever it is CS students do these days.

The city is made up of ~n~ train stations, numbered from ~1~ to ~n~. You live at station ~1~, and your workplace is at station ~n~. Some pairs of stations are connected by train lines, and each line takes a fixed number of minutes to travel in either direction.

Note: You can move between any two directly connected stations immediately. You are not allowed to wait — as soon as you arrive at a station, you must board a train to a neighboring station (if possible).

You want to seem professional on your first day. What do professionals do? They arrive to work at a professional-looking time! You have decided that a "professional-looking time" ends in either a ~5~ or ~0~, so:

• 7:00 and 9:35 are professional-looking times.
• 7:01 and 4:12 are not.

What is the earliest, professional-looking time you are able to arrive at your workplace?

Note: You are allowed to arrive at a non-professional-looking time, but you will need to leave and come back again.

Input

The first line consists of a time ~t~, the time you will leave your house. This time is ~24~-hours, and will be in the form HH:MM.

The second line consists of an integer ~n~ ~(1 \leq n \leq 10^4)~, the number of train stations in the city.

The third line consists of an integer ~m~ ~(1 \leq m \leq 10^4)~, the number of connections between the stations.

The next ~m~ lines are in the form ~a \; b \; s~, signifying that it will take ~s~ minutes to travel between stations ~a~ and ~b~.

Output

Output the earliest, professional-looking time you are able to arrive at the office, in ~24~-hour format, and in the form HH:MM.

Note: If you leave your home at 23:00, arriving to the office at 23:30 is faster than arriving at 00:00, even though 00:00 "looks" smaller. It is about the total time you take!

If this is not possible to arrive at the office at a professional-looking time, output ~-1~.

Note: There might not be any trains connecting you to your work.

Example

Input

07:01
4
4
1 2 2
1 3 1
2 4 7
3 4 4

Output

07:10

Travel from station ~1~ to station ~2~ in ~2~ minutes.

Travel from station ~2~ to station ~4~ in ~7~ minutes.

You arrive to work at 07:10, which is the earliest possible, professional-looking time.

Input

10:00
3
2
1 2 1
2 3 2

Output

10:05

Travel from station ~1~ to station ~2~ in ~1~ minute.

Travel from station ~2~ to station ~1~ in ~1~ minute.

Travel from station ~1~ to station ~2~ in ~1~ minute.

Travel from station ~2~ to station ~3~ in ~2~ minutes.

You arrive to work at 10:05, which is the earliest possible professional-looking time.

Input

2:01
2
1
1 2 5

Output

-1

It is not possible to ever arrive to work at a professional-looking time.