蓝桥杯2023年第十四届省赛真题-独一无二

输入的第一行包含两个正整数 n, m。 

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

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

0
0
0
1

在给定的图中，只有 s₄ 一开始为 2，因为有两条最短路：1 → 2 → 4, 1 → 3 → 4，任意删掉一条边后，就可以只剩一条最短路。 

对于 30% 的评测用例，n ≤ 1000； 对于所有评测用例，n ≤ 10⁵ ，0 ≤ m ≤ min{ n(n−1)/2 , 10⁶ } ，1 ≤ u_i , v_i ≤ n ， 1 ≤ c_i ≤ 10 。