Between attending classes, playing in rehearsals, and eating food, Capba
has quite the busy university schedule. The campus consists of
locations, numbered from
to
, with
paths, numbered from
to
, running amongst them. Path
directly connects locations
and
,
and takes
minutes to
traverse in either direction. These paths are the only way to travel
between locations.
Today, Capba has
engagements, numbered from
to
. Engagement
takes place at location
,
starting
minutes after the start of the day, and
lasting
minutes
. Yes, it's a
particularly long day. The engagements are numbered in increasing order
of their start times, and no two will start at the same time.
Capba leaves location
(his residence) at time zero. It's possible that
he won't be able to make it to everything, due to the lengths of the
engagements as well as the travel times in between them. Capba decides
that he's not feeling particularly dynamic today, and adopts the
following strategy: Once at an engagement, he sits through it until it's
over, and then he walks to the next engagement which he can make it to
on time (or early). (He may also choose not to walk at all, if the next
engagement's location is the same as his current location.)
Given Capba's busy schedule, determine which engagements he will end up
attending.
Input Specification
Line
:
,
.
Next
lines:
,
,
.
Next line:
.
Next
lines:
,
,
.
All values are integers.
Output Specification
One per line, the numbers of the engagements which Capba will honour, in
increasing order.
Sample Input
Copy
5 5
1 2 10
5 1 2
3 5 6
2 4 3
4 5 4
6
1 5 5
5 12 1
2 20 100
3 77 100
1 129 2
4 136 10
Sample Output
Copy
1
2
3
5
Explanation
Capba starts at location
, and is there from time
until time
.
He then walks to location
, arriving early for engagement
. He remains
there until time
.
He then walks to location
, via location
, arriving just on time for
engagement
, which lasts until time
.
Meanwhile, he must skip engagement
.
Following paths through locations
and
, Capba can barely make it on
time to engagement
, which runs from time
to time
.
However, it takes at least
minutes to reach location
from location
, so he cannot make it to engagement
on time and must skip it.
Comments