给定一个包含 个点， 条边的无向图，每条边的边权均为 。
再给定 个三元组 ，表示从 点走到 点后不能往 点走。注意三元组是有序的，如可以从 点走到 点再走到 。
现在你要在 个三元组的限制下，找出 号点到 号点的最短路径，并输出任意一条合法路径，会有 Check 检查你的输出。
输入文件第一行有三个数 ，，，意义如题目所述。
接下来 行每行两个数 ，，表示 ， 间有一条边。
再下面 行，每行三个数 描述一个三元组。
输出文件共两行数，第一行一个数 表示最短路径长度。
第二行 个数，表示从 到 所经过的节点。
4 4 2 1 2 2 3 3 4 1 3 1 2 3 1 3 4
4 1 3 2 3 4
对于 的数据满足 ，，。
