Description

Yazid 最近沉迷于一款冒险类游戏无法自拔。 这款游戏的地图可以抽象成一张包含 n 个节点 m 条边的无向图（节点和边的编号均从 1 开始），每条边带有边权，也就是说通过每条边所需的时间不尽相同。 Yazid 接到了 k 个副本任务，每个任务都要求 Yazid 进入一个独一无二的副本挑战 Boss。 其中，第 i 个任务（1 ≤ i ≤ k）的副本入口在节点 ui，其入. 口. 开. 放. 时. 间. 为 [li, ri]，换而言之，Yazid 需要在规定时间内到达（或等候在）节点 ui，才能进入副本，挑战 Boss。 除此之外，每个副本的难度对于 Yazid 而言也不尽相同，经过精确的计算，Yazid 成功挑战第 i 个副本所需的时间为 ti，也就是说，如果 Yazid 在 T 时刻进入副本 i，那么他将在 T + ti 时刻将 Boss 挑落马下，并继续他的征程。 需要注意的是，入口开放时间只对玩家的进入副本时间作出限制，玩家仅仅被要求 在入口关闭前进入副本，并不被要求在入口关闭前完成 Boss 挑战。 每个任务的重要程度也是不尽相同的。完成第 i 个任务可以获得 ci 个金币的奖励。在第 0 时刻，Yazid 的角色身处节点 1。 请问，假设 Yazid 的策略安排得当，他总共最多能够获得多少金币奖励呢？

Input Format

从文件 instance.in 中读入数据。 第 1 行 2 个用单个用单个空格隔开的正整数 n, m，分别表示图的节点数、边数。 接下来 m 行，每行 3 个用单个空格隔开的整数 x, y, z，描述一条连接节点 x, y 的、 需要花 z 单位时间通过的无向边。 • 在这里，我们保证 1 ≤ x, y ≤ n。 接下来 1 行 1 个正整数 k，表示副本任务的数量。 接下来 k 行，每行 5 用单个空格隔开的整数 ui, li, ri, ti, ci 描述一个任务，意义见 【题目描述】。 • 在这里，我们保证 1 ≤ ui ≤ n，li ≤ ri。

Output Format

输出到文件 instance.out 中。 输出一行一个整数，表示 Yazid 最多能够获得的奖励金币数目。

Sample

【样例 1 输入】

3	2	
1	2	10
2	3	10
2		
1	0	50 20 1
2	0	39 20 1

【样例 1 输出】

2

【样例 1 解释】

Yazid 应先前往 2 号节点执行第 2 个任务，然后再回到 1 号节点执行第 1 个任务，
才能同时完成 2 个任务。

【样例 2 输入】

4	6	
1	2	1
1	3	5
1	4	10
2	3	2
2	4	3
3	4	15
3		
1	0	20   2   1
3	4	20   6   2
4   15  15   2   2

【样例 2 输出】

4

【样例 2 解释】

Yazid 可以依次完成任务 2, 3，但如若这么做，他将不得不错过任务 1，因此他最多只能获得 4 个金币。

【样例 3】

见选手目录下的 instance/instance3.in 与 instance/instance3.out。

【子任务】

详见PDF

Hint

对于所有测试点，保证 n ≤ 200，m ≤ 20, 000，k ≤ 18，1 ≤ z ≤ 10^4，0 ≤ li, ri, ti ≤ 10^7， ci ≤ 10^4。