U331150 密室逃脱2

小H 这次又被可恶的 小Y 抓走了，这次 小Y 吸取了上次的教训，把 小H 带到了一个防守更加严密的密室，这次 小H 能否逃出去呢……

这一次的密室由 $n$ 个站点和一些道路组成，小Y 还是一如既往的狠心，在密室的四周建立起了高墙和大门，小Y 把钥匙放藏各个站点上，每个站点有一把钥匙，大门需要 $n$ 把钥匙才能打开。 但 小H 这次早有准备，在他被押进密室的时候为自己留下了必需的 **能量补给用具**，但是他哪里想得到这次密室这么大，所以他迫不得已选择一些站点存放 **能量补给用具**，可是在不同站点（偷偷）存放 **能量补给用具** 所需要的精力是不同的，在第 $i$ 个站点存放需要 $w_i$ 的体力值。 在 小H 的逃离过程中，经过道路是不可避免的，但是不同的道路 小H 也会消耗不同的体力，站点 $i$ 到 $j$ 连接的道路需要消耗 小H $p_{i, j}$ 的体力值。 无可奈何之下，小H 找到了你，想让你帮他设计一种逃离方案，把 **能量补给用具** 存放在一些站点上，让 小H 在尽可能的节省体力的情况下逃离这个密室。 小H 的行动必须依靠 **能量补给用具** 的能量，否则无法逃离。 **PS:** 每个站点最多只能存放一个 **能量补给用具** 。

无

无

#### 样例解释： 小H 可以选择在 $1$ 号站点存放 **能量补给用具**，与各个站点连通，最小体力值消耗为 $2 + 2 + 1 = 5$ 。 --- 对于 $40\%$ 的数据，$1 \leq n \leq 300$，$1 \leq w_i, p_{i, j} \leq 25$ 对于 $100\%$ 的数据，$1 \leq n \leq 2000$，$1 \leq w_i, p_{i, j} \leq 800$