U458685 蓝巾起义

公元 202 年，农民起义领袖林登万将军发动了"蓝巾起义"，力图推翻帝国的统治。

帝国由 $n$ 座城市组成，城市依次编号为 $1\sim n$，城市之间有 $m$ 条双向道路相连，任意两个城市间只有一条道路直接相连，并且我们知道任意两个城市是相通的（但可能需要途经其他城市）。 林将军只需要攻占其中 $k$ 座重要城市 ，起义即可胜利。我们知道这 $k$ 座重要城市 的编号恰好为 $1\sim k$。起义军攻占 $i$ 号城市需要花费 $a_i$ 天（$1\le i\le k$），通过第 $i,j$ 个城市之间的道路则要花费 $b_{i,j}$ 天（$1\le i \lt j \le n$）。 林将军的计划是这样的： - 首先，选择一个重要城市最先发动起义，当攻占这个城市后，起义军会在城市的每条相邻道路上派出一支新部队，继续前进。 - 之后每当起义军到达一个城市后，都会向城市每条相邻道路上派出一支部队继续前进，但当这是一个还未被攻占的重要城市时，起义军需要先花费时间攻占这个城市，之后才能出发。 - 分兵不会影响起义军攻占城市和在道路上移动所需的时间。 林将军想问作为军师的你，他至少要花几天时间起义才能胜利？你要告诉他最少的天数，以及为此他应该在哪个城市最先发动起义。

输入文件共 $m + 2$ 行。 第一行，三个正整数 $n,m,k$，分别表示城市数目、道路数目和重要城市的数目。 第二行，用单个空格隔开的 $k$ 个正整数 $a_1,a_2,\cdots,a_k$，依次为攻占 $1\sim k$ 号城市所需天数。 之后 $m$ 行，每行三个用单个空格隔开的正整数 $x,y,b$，表示编号为 $x,y$ 的两个城市之间有一条道路，通过需要 $b$ 天。

输出文件只有一行，包括两个用单个空格隔开的整数 $s,d$。 $s$ 表示你选择的起始城市，$d$ 表示起义胜利所需的最小天数。（如有多个城市都能达到最小天数，选择编号最小的）

| 测试点 | $k$ | $n$ | $m$ | 图的形状 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1\sim2$ | $k=1$ | $5\le n\le10$ | $m=\frac{n(n-1)}{2}$ | 完全图 | | $3\sim6$ | $1\le k\le50$ | $5\le n\le 100$ | $m=n-1$ | 一条链 | | $7\sim10$ | $1\le k\le50$ | $5\le n\le 400$ | $m=n-1$ | 无环连通图 | | $11\sim14$ | $1\le k\le50$ | $5\le n\le 400$ | $n-1\le\frac{n(n-1)}{2}$ | 连通图 | | $15\sim20$ | $1\le k\le50$ | $5\le n\le 5000$ | $n-1\le m\le300000$ | 连通图 | 对于 $100\%$ 的数据，满足 $k\le n,1\le a_i\le50000,1\le b_{i,j}\le2000$。