牛牛所在的W市是一个不太大的城市，城市有n个路口以及m条公路，这些双向连通的公路长度均为1，保证你可以从一个城市直接或者间接移动到所有的城市。牛牛在玩宝可梦Go，众所周知呢，这个游戏需要到城市的各个地方去抓宝可梦，假设现在牛牛知道了接下来将会刷出k只宝可梦，他还知道每只宝可梦的刷新时刻、地点以及该宝可梦的战斗力，如果在宝可梦刷新时，牛牛恰好在那个路口，他就一定能够抓住那只宝可梦。 由于游戏公司不想让有选择恐惧症的玩家为难，所以他们设计不存在任何一个时刻同时刷出两只及以上的宝可梦。 假设不存在任何一个时刻会同时刷出两只宝可梦，牛牛一开始在城市的1号路口，最开始的时刻为0时刻，牛牛可以在每个时刻之前移动到相邻他所在位置的路口，当然他也可以保持原地不动，他现在想知道他能够捕获的宝可梦战斗力之和最大为多少？

输入描述:

第一行输入两个正整数n,m,表示城市的路口数目以及公路数目。接下来m行每行两个正整数u,v表示一条长度为1链接两个路的公路。接下来一行输入一个正整数k表示宝可梦的数目。接下来输入k行，每行三个正整数，分别表示宝可梦刷新的时间、地点、以及战斗力，输入数据保证不会出现在同一时刻刷出多只宝可梦。

输出描述:

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

备注:

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