P1811 最短路

给定一个包含 $N$ 个点，$M$ 条边的无向图，每条边的边权均为 $1$。 再给定 $K$ 个三元组 $(A,B,C)$，表示从 $A$ 点走到 $B$ 点后不能往 $C$ 点走。注意三元组是有序的，如可以从 $B$ 点走到 $A$ 点再走到 $C$。 现在你要在 $K$ 个三元组的限制下，找出 $1$ 号点到 $N$ 号点的最短路径，并输出任意一条合法路径，会有 Check 检查你的输出。

无

无

对于 $40\%$ 的数据满足 $N \le 10$，$M \le 20$，$K \le 5$。 对于 $100\%$ 的数据满足 $N \le 3000$，$M \le 20000$，$K \le 100000$。