Flash 是 A 城里的一位快递小哥，A 城中共有 家住户，门牌号依次为 ，它们通过 条双向道路相连。Flash 位于的快递站门牌号为 ，保证可以到达 A 城中的任意一家住户。

Flash 今天（第一天）接到了一个派送任务，需要向每一家住户派送一个神秘快递，但是 Flash 的能力有限，每天只能派送一件快递且只能从快递站出发。每一件快递都标明了一个截止日期，Flash 需要在第 个快递的截止日期 前将该快递送至门牌号为 的住户手中。例如，若在第 天，某个未被派送快递的截止日期为 ，当天派送它则可以成功送达，但如果同时有两个截止日期为 的未被派送的快递，那么 Flash 只能选择一个进行派送，另外一个必定超时。

对于每一件快递而言，其派送费等于最短派送路径的长度。但是，若某个快递超时，Flash 将会被处以相应派送费金额的罚款，并且不会得到任何派送费！

收益指总派送费减总罚款，请你帮忙计算出 Flash 此次任务的最大收益为多少？

第一行输入两个整数 。

接下来  行，每行输入三个整数  表示  号住户与  号住户之间有一条长度为  的道路。

第  行输入  个数  表示第  个快递的截止时间。

输出一个整数，表示 Flash 的最大收益。

3 3
0 1 3
0 2 6
0 3 9
3 1 1

6

5 10
0 2 12
2 4 32
2 5 4
5 4 19
4 1 6
0 1 6
3 0 10
1 2 2
1 3 32
3 5 5
1 3 4 3 1

36