某个外国探险队在非洲沙漠中发现了二战时期希特勒埋藏的n个地下宝库(编号为1…n)，并且还记下了从一个宝库走到另一个宝库的时间(有的宝库之间无通路，无通过时间)。几经知道每个宝库中藏有一定数量的宝藏，但由于德国法西斯在建造宝库时设有保护措施，因而每个宝库只能进入通过一次。在第一个宝库内可以取得打开其它宝库的钥匙(第一个宝库可以不用钥匙就进入)。另外，探险队还发现，在进入第一个宝库的同时将触发一个爆破装置，因而所有的宝库将在tk秒后同时爆炸。
请你设计一种最佳的从1开始的取宝藏的方案，使在宝库爆炸前(包括爆炸时)能取得最多的宝藏。
例：有4个宝库：1、2、3、4
其中宝藏数量为：100，60，80，70
通过时间(没有给出通过时间的表示无通路)：
1—2 20秒
1—3 30秒
2—4 20秒
3—4 15秒
爆炸时间：50秒
此时方法有：
| 1—2—4 | 计40秒，可取100+60+70=230 |
或：
| 1—3—4 | 计45秒，可取100+80+70=250 |
则最佳方案为：
| 1—3—4 | 可取宝藏250 |
包含多个测试数据，每个测试数据的第一行有三个用空格隔开的整数n(1≤n≤20), k(1≤k≤50), tk(1≤tk≤1000)。
其中n表示宝库的数目，k表示由k个通路，tk表示爆炸的时间。
接下来k行，每行有三个数据(x, y, t)，表示从x→y或y→x所需时间t(即无向图)。
最后一行有n个整数，表示宝库中的宝藏数。
一行单独的一个0表示输入结束。
每行一个数，表示能取到的最多的宝藏数。
4 4 50 1 2 20 1 3 30 2 4 20 3 4 15 100 60 80 70 0
250