Busy Schedule

Between attending classes, playing in rehearsals, and eating food, Capba has quite the busy university schedule. The campus consists of N (1 ≤ N ≤ 200) locations, numbered from 1 to N, with M (1 ≤ M ≤ 1000) paths, numbered from 1 to M, running amongst them. Path i directly connects locations A_i and B_i (1 ≤ A_i, B_i ≤ N), and takes C_i (1 ≤ C_i ≤ 50000) minutes to traverse in either direction. These paths are the only way to travel between locations.

Today, Capba has K (1 ≤ K ≤ 10000) engagements, numbered from 1 to K. Engagement i takes place at location L_i (1 ≤ L_i ≤ N), starting T_i minutes after the start of the day, and lasting D_i minutes (1 ≤ T_i, D_i ≤ 10⁹). 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 1 (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 Format

Line 1: N, M

Next M lines: A_i, B_i, C_i

Next line: K

Next K lines: L_i, T_i, D_i

All values are integers.

Output Format

One per line, the numbers of the engagements which Capba will honour, in increasing order.

Sample Input

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

Explanation

[insert diagram if possible]

Sample Output

1
2
3
5

Explanation

Capba starts at location 1, and is there from time 0 until time 10.

He then walks to location 5, arriving early for engagement 2. He remains there until time 13.

He then walks to location 2, via location 4, arriving just on time for engagement 3, which lasts until time 120.

Meanwhile, he must skip engagement 4.

Following paths through locations 4 and 5, Capba can barely make it on time to engagement 5, which runs from time 129 to time 131.

However, it takes at least 6 minutes to reach location 4 from location 1, so he cannot make it to engagement 6 on time and must skip it.

All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 1024M
Added: Feb 22, 2011
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)