题目描述

在这个世界中共有 N 座城市，编号为 1 到 N。你有 M 种不同的交通工具可供使用，它们在城市之间提供双向连接。其中有些交通工具是公交车，另一些是飞机。

你的目标是从城市 1 到达城市 N，并且使用的交通工具数量尽可能少。

但很遗憾，你最多只能乘坐 K 次飞机，其中 K 只可能是 1 或 2。请输出所需交通工具的最少数量；如果无法到达，则输出 -1。

输入格式

标准输入第一行包含三个整数 N、M、K，分别表示城市数量、交通工具数量，以及最多允许使用的飞机数量。

接下来 M 行，每行包含三个整数 a_i、b_i、t_i（1 ≤ a_i,b_i ≤ N，1 ≤ t_i ≤ 2），其中：

• t_i = 1 表示公交车；
• t_i = 2 表示飞机。

该交通工具连接城市 a_i 与城市 b_i。

输出格式

输出一个整数，表示从城市 1 到城市 N 所需的最少交通工具数量；若无法到达则输出 -1。

数据范围

• 2 ≤ N ≤ 2 × 10^5
• 1 ≤ M ≤ 3 × N
• 1 ≤ K ≤ 2

子任务

只有当某个子任务及其所依赖的全部子任务全部通过时，才能获得该子任务的分数。

样例 #1

输入 #1

5 5 1
1 2 1
2 3 1
3 5 2
2 4 1
4 5 2

输出 #1

3

说明 #1

一种最优路径为：1 → 2 → 3 → 5。

样例 #2

输入 #2

4 3 2
1 2 1
2 3 2
3 4 1

输出 #2

3

说明 #2

最优路径为：1 → 2 → 3 → 4。我们乘坐了 1 次飞机，尽管允许使用的最大飞机数是 2。

样例 #3

输入 #3

3 2 1
1 2 2
2 3 2

输出 #3

-1

说明 #3

无法从城市 1 到达城市 3，因为 K < 2。