P3393 逃离僵尸岛

小 a 住的国家被僵尸侵略了！小 a 打算逃离到该国唯一的国际空港逃出这个国家。 该国有 $N$ 个城市，城市之间有道路相连。一共有 $M$ 条双向道路。保证没有自环和重边。 其中 $K$ 个城市已经被僵尸控制了，如果贸然闯入就会被感染 TAT...所以不能进入。由其中任意城市经过不超过 $S$ 条道路就可以到达的别的城市，就是危险城市。换句话说只要某个城市到任意被僵尸控制的城市距离不超过 $S$，就是危险的。 小 a 住在 $1$ 号城市，国际空港在 $N$ 号城市，这两座城市没有被侵略。小a走每一段道路（从一个城市直接到达另外一个城市）得花一整个白天，所以晚上要住旅店。安全的的城市旅馆比较便宜要 $P$ 元，而被危险的城市，旅馆要进行安保措施，所以会变贵，为 $Q$ 元。所有危险的城市的住宿价格一样，安全的城市也是。在 $1$ 号城市和 $N$ 城市，不需要住店。 小 a 比较抠门，所以他希望知道从 $1$ 号城市到 $N$ 号城市所需要的最小花费。 输入数据保证存在路径，可以成功逃离。输入数据保证他可以逃离成功。

无

无

 对于 $20\%$ 数据，$N\le 50$。 对于 $100\%$ 数据，$2\le N\le 10^5$，$1\le M\le 2\times 10^5$，$0\le K\le N - 2$，$0\le S\le 10^5$，$1\le P< Q\le 10^5$。