Вам дається ненаправлений зв’язний граф з \(N\) вершин i \(M\) ребер, що не мiстить нi петлі, нi подвiйних ребер. \(i\)-е \((1 \le i \le M )\) ребро з’єднує вершину \(a_i\) та \(b_i\) шляхом \(c_i\) . Подвiйнi ребра - це два ребра, де \((a_i , b_i ) = (a_j , b_j )\) або \((a_i , b_i ) = (b_j , a_j )\) \((1 \le i < j \le M)\).

Зв’язний граф означає, що мiж будь-якою парою вершин цього графа iснує шлях.

Знайдiть кiлькiсть ребер, якi не мiстяться в жодному найкоротшому шляху мiж будь-якою парою рiзних вершин.

Формат вхiдних даних

Перший рядок вхiдного потоку мiстить два цiлi числа \(N, M\) \((2 \le N \le 100\), \(N − 1 \le M \le min(N \cdot (N − 1)/2, 1000))\), якi роздiляються пропуском.

Далi, у наступних \(M\) рядках мiстяться трiйки цiлих чисел \(a_i, b_i, c_i\) \((1 \le a_i, b_i \le N,\) \(1 \le c_i \le 1000)\), якi також роздiляються пропуском.

Формат вихiдних даних

Виведiть кiлькiсть ребер графу, якi не мiстяться в жодному найкоротшому шляху мiж будь-якою парою рiзних вершин.

Приклад вхідних даних

3 3
1 2 1
1 3 1
2 3 3

Приклад вихідних даних

1