牛牛的宝可梦Go

题号：NC201847
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

牛牛所在的W市是一个不太大的城市，城市有n个路口以及m条公路，这些双向连通的公路长度均为1，保证你可以从一个城市直接或者间接移动到所有的城市。牛牛在玩宝可梦Go，众所周知呢，这个游戏需要到城市的各个地方去抓宝可梦，假设现在牛牛知道了接下来将会刷出k只宝可梦，他还知道每只宝可梦的刷新时刻、地点以及该宝可梦的战斗力，如果在宝可梦刷新时，牛牛恰好在那个路口，他就一定能够抓住那只宝可梦。

由于游戏公司不想让有选择恐惧症的玩家为难，所以他们设计不存在任何一个时刻同时刷出两只及以上的宝可梦。

假设不存在任何一个时刻会同时刷出两只宝可梦，牛牛一开始在城市的1号路口，最开始的时刻为0时刻，牛牛可以在每个时刻之前移动到相邻他所在位置的路口，当然他也可以保持原地不动，他现在想知道他能够捕获的宝可梦战斗力之和最大为多少？

输入描述:

第一行输入两个正整数n,m, $(1 \leq n \leq 200,0 \leq m \leq 10^4)$ 表示城市的路口数目以及公路数目。

接下来m行每行两个正整数u,v $(1 \leq u,v \leq n)$ 表示一条长度为1链接两个路的公路。

接下来一行输入一个正整数k $(1 \leq k \leq 10^5)$ 表示宝可梦的数目。

接下来输入k行，每行三个正整数 $t_i,p_i,val_i(1 \leq p_i \leq n,1 \leq t_i,val_i \leq 10^9)$ ，分别表示宝可梦刷新的时间、地点、以及战斗力，输入数据保证不会出现在同一时刻刷出多只宝可梦。

输出描述:

输出一个整数表示牛牛能捉到的宝可梦战斗力之和最大是多少。

示例1

输入

复制

输出

复制

示例2

输入

复制

1 0
3
1 1 100
100 1 10000
10000 1 1

输出

复制

示例3

输入

复制

3 2
1 2
2 3
1
1 3 1000000000

输出

复制

示例4

输入

复制

3 2
1 2
2 3
1
1 2 1000000000

输出

复制

1000000000

备注:

输入数据保证不会出现在同一时刻刷出多只宝可梦。