輸入的第一行包含兩個(gè)正整數(shù) n, m。 

接下來(lái) m 行，每行包含三個(gè)正整數(shù) u_i , v_i , c_i 表示第 i 條邊連接的兩個(gè)點(diǎn)的編號(hào)和邊權(quán)。 

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

0
0
0
1

在給定的圖中，只有 s₄ 一開(kāi)始為 2，因?yàn)橛袃蓷l最短路：1 → 2 → 4, 1 → 3 → 4，任意刪掉一條邊后，就可以只剩一條最短路。 

對(duì)于 30% 的評(píng)測(cè)用例，n ≤ 1000； 對(duì)于所有評(píng)測(cè)用例，n ≤ 10⁵ ，0 ≤ m ≤ min{ n(n?1)/2 , 10⁶ } ，1 ≤ u_i , v_i ≤ n ， 1 ≤ c_i ≤ 10 。