P3489 [POI 2009] WIE-Hexer

Byteasar 成为了一名猎魔人——一个征服怪物的人。 目前他要返回他的家乡 Byteburg。可惜回家的路要经过一个充满野兽的土地。幸运的是，当地居民被迫与怪物斗争了几个世纪，已经掌握了锻造的艺术——他们现在能够制造出对抗野兽非常有效的特殊剑。 Byteasar 所经过的土地相当广阔：那里有许多城镇，许多道路连接着它们。 这些道路不会在城镇外交叉（主要是因为其中一些是地下通道）。 Byteasar 已经收集了关于这片土地的所有实用信息（所有猎魔人都喜欢知道这些事情）。 他知道在每条路上可能遇到的怪物种类，以及他需要多少时间才能走完这条路。 他还知道在哪些村庄有铁匠，以及他们制作的剑对哪些种类的怪物有效。 Byteasar 想尽快回到 Byteburg。 作为一个猎魔人，他对自己不知道最佳路线感到相当羞愧，而且他目前身上没有剑。 帮助他找到到 Byteburg 的最短路径，以便每当他可能遇到某种怪物时，他之前就有机会获得一把合适的剑来对抗野兽。 你不需要担心剑的数量或重量——每个猎魔人都像牛一样强壮，所以他可以携带（几乎）无限数量的装备，特别是剑。

标准输入的第一行包含四个整数：$n,m,p,k$ ($1\le n\le 200,0\le m\le 3000,1\le p\le 13,0\le k\le n$)，它们分别表示： 城镇的数量，连接它们的道路数量，不同种类的怪物数量和铁匠的数量。 城镇从 $1$ 到 $n$ 编号，其中 $n$ 是 Byteburg 的编号，$1$ 是 Byteasar 开始的村庄编号。怪物种类从 $1$ 到 $p$ 编号。 接下来的 $k$ 行给出了连续铁匠的资料，每行一个。第 $(i+1)$ 行包含整数 $w_i,q_i,r_{i,1}

你的程序应输出一个整数到标准输出——到达 Byteburg 所需的最短总时间。 如果无法到达 Byteburg，则该数字应为 $-1$。

题面翻译由 ChatGPT-4o 提供。