P12384 [蓝桥杯 2023 省 Python B] 独一无二【疑似假题】

有一个包含 $n$ 个点，$m$ 条边的无向图，第 $i$ 条边的边权为 $c_i$，没有重边和自环。设 $s_i$ 表示从结点 1 出发到达结点 $i$ 的最短路的不同路径数 $(i \in [1, n])$，显然可以通过删除 $a_i$ 条边使得 $s_i = 1$，也就是有且仅有一条从 1 到 $i$ 的最短路，且保持最短路的路径长度不变，求出 $a_n$ 的最小值。

输入的第一行包含两个正整数 $n, m$。 接下来 $m$ 行，每行包含三个正整数 $u_i, v_i, c_i$ 表示第 $i$ 条边连接的两个点的编号和边权。

输出一行包含一个正整数表示答案，如果 1 和 $n$ 不连通，输出 -1 。

### 样例说明 在给定的图中，只有 $s_4$ 一开始为 $2$，因为有两条最短路：$1 \rightarrow 2 \rightarrow 4, 1 \rightarrow 3 \rightarrow 4$，任意删掉一条边后，就可以只剩一条最短路，且保持最短路的路径长度不变。 ### 评测用例规模与约定 - 对于 $30\%$ 的评测用例，$n \leq 18$； - 对于所有评测用例，$n \leq 100$，$0 \leq m \leq \min\{\frac{n(n-1)}{2}, 2000\}$，$1 \leq u_i, v_i \leq n$，$1 \leq c_i \leq 2$。