12956번 - 퍼레이드

N개의 교차로와 M개의 거리로 이루어진 도시가 있다. 교차로는 0번부터 N-1번까지 번호가 매겨져 있고, 도로는 0번부터 M-1번까지 번호가 매겨져 있다. 모든 도로는 양방향이며, 도로는 서로 다른 교차로를 연결한다. 임의의 두 교차로는 최대 1개의 도로로 연결되어 있다. 모든 교차로는 연결되어 있기 때문에, 한 교차로에서 다른 교차로로 도로를 이용해서 항상 갈 수 있다.

도시의 시장은 퍼레이드를 개최하려고 한다. 퍼레이드는 도로 하나에서 열린다. 

도시에는 모든 교차로의 쌍(X, Y) 마다 X와 Y를 오가는 버스가 존재한다. 퍼레이드는 버스의 운행에 영향을 줄 수 있다. 버스가 퍼레이드에 영향을 받는 경우는 퍼레이드에 사용하는 도로를 제외하고 구한 최단 거리의 길이가 제외하지 않고 구한 X에서 Y로 가는 최단 경로의 길이보다 큰 경우이다. 퍼레이드 때문에 X에서 Y로 갈 수 없게 되는 경우도 영향을 받는 경우이다.

각 도로에서 퍼레이드를 개최한다고 했을 때, 영향을 받는 버스 노선의 수가 몇 개인지 구하는 프로그램을 작성하시오.

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 100)과 도로의 개수 M (1 ≤ M ≤ 2,000)이 주어진다.

둘째 줄부터 M개의 줄에는 도로의 정보가 0번 도로부터 순서대로 주어진다.

도로의 정보는 from, to, time으로 이루어져 있으며, from과 to를 오가는데 걸리는 시간이 time이라는 뜻이다. (0 ≤ from, to ≤ N-1, 1 ≤ time ≤ 1,000, from ≠ to)

각 도로에서 퍼레이드가 열린다고 했을 때, 영향을 받는 버스 노선의 개수를 0번 도로부터 순서대로 공백으로 구분해 출력한다.