狼的复仇
时间限制：1秒 内存限制：256M
【问题描述】
山谷里有 \(n\) 座森林，这些森林从 1 到 \(n\) 编号。某些森林之间有小路相连，总共 \(m\) 条小路连通了这 \(n\) 座森林，任意两座森林之间都有至少一条路径可以互相到达。
很久很久以前，这里是狼的家园。在每一座森林里都有一匹狼，每一匹狼都静静地守护着它所在的森林。直到有一天，人类出现了。它们疯狂地开垦 1 号森林，并且杀死了 1 号森林的狼。以后，这座森林就好像属于人类了一样，不时有人来到 1 号森林。其余的 \(n-1\) 匹狼不愿看到悲剧再次发生，它们希望集合它们的力量，为种族，为大自然报仇。
机会来了。一次偶然的机会，大灰狼们获得了一个重要的情报——有一个小MM经常独自游荡于 1 号森林。消息传遍了整个狼群，小MM细腻的皮肤和鲜嫩的肉令它们的血液沸腾起来，每一匹狼都幻想着能扑上前去撕裂MM的身体，舔拭那温热的血液。唯一的问题是，它们需要尽快察觉小MM的出现并快速奔向目的地。但由于山谷地形复杂，在第一时间里观察到小MM的出现谈何容易。因此，狼群计划在某些森林建立瞭望塔。当小MM再次出现在 1 号森林里时，所在的森林里有瞭望塔的狼可以立即发现这一情况，并且沿着最短路径奔向MM。有时最短路不止一条，在途中每当有多条路可以选择时，狼总会选择前往编号较小的森林。这些狼的行动将唤起最短路上沿途经过的狼，这些最短路上的狼将会闻声而起，一同对MM发起进攻。每匹狼都有自己的攻击力，最终对小MM的攻击力即是所有到达 1 号森林的狼的攻击力总和。注意攻击力的值有可能为负数，因为有一些狼很可能会“拖后腿”，对整个种族的复仇计划反而不利。
由于森林的地形不同，在不同的地方建造瞭望塔需要的材料不同。现在狼群里一共有 \(k\) 个单位的建筑材料，并且它们已经计算出在 \(n-1\) 座森林中建造瞭望塔各自需要的材料数目。请你来计算一下，在哪些森林里建造瞭望塔可以使得最终到达 1 号森林的狼群攻击力总和最大。当然，建筑材料不一定要全部用完，但你的方案所需要的建筑材料不能超过总的材料数 \(k\)。
【输入格式】
第一行输入三个用空格隔开的正整数 \(k, n, m\)，分别表示材料的总数量，森林的数量和小路的数量。1 号森林总是MM出没的地方，其余 \(n-1\) 座森林是狼所在的地方。
第二行到第 \(n\) 行每行有两个用空格隔开的整数，依次表示 2 号森林到 \(n\) 号森林里的狼的攻击力和在这里建造瞭望塔所需要的材料数。狼的攻击力绝对值不超过 10000（可能为负数），每个瞭望塔的材料耗费都是不超过 100 的正整数。
接下来 \(m\) 行每行有三个用空格隔开的数 \(x,y,d\)，表示在 \(x\) 森林和 \(y\) 森林之间存在一条长度为 \(d\) 的路。路的长度是不超过 10000 的正整数。
【输出格式】
输出在满足材料数限制下建造瞭望塔，最多可以给MM带去多大的攻击力。
【输入输出样例】
Input
8 7 10
1 4
1 2
2 4
-3 5
9 4
2 1
1 4 2
4 3 4
2 3 3
5 1 2
2 4 1
1 2 3
6 7 1
2 7 4
2 6 8
5 6 5
Output
10
【样例解释】
输入数据如下图所示，我们用AP来表示攻击力，用 \(cost\) 来表示瞭望塔的材料花费。在涂有蓝色的节点上建造瞭望塔花费仅为 7，由于 7<=8，因此这种方案未超过材料预算。我们下面计算这种方案所带来的攻击力。
这三匹狼的行走路线已经用箭头表示了出来。注意 3 号森林和 7 号森林的狼有多个到达节点 1 的最短路径，它总是选择标号较小的节点前进。这些路线经过了两个绿色的节点，这两个绿色的节点所对应的狼的攻击力也将加入总攻击力中（必须加入计算且仅算一次）。这种方案的攻击力为 1+1+2+9-3=10。事实上，攻击力最大为 10，没有其它的建造方案使得总攻击力大于 10 且材料花费不超过 8。
【数据限制】
对于 \(30\%\) 的数据， \(k≤1，n≤10， m≤100\)
对于 \(50\%\) 的数据， \(k≤10，n≤100， m≤1000\)
对于 \(100\%\) 的数据，\(k≤100，n≤1000， m≤10000\)
