시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 76 32 28 43.750%

문제

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번 도로부터 순서대로 공백으로 구분해 출력한다.

예제 입력 1

3 2
0 1 1
1 2 1

예제 출력 1

2 2

예제 입력 2

4 3
0 1 2
1 2 4
2 3 6

예제 출력 2

3 4 3

예제 입력 3

5 10
0 1 1
0 2 2
0 3 3
0 4 4
1 2 5
1 3 6
1 4 7
2 3 8
2 4 9
3 4 10

예제 출력 3

4 4 4 4 0 0 0 0 0 0

예제 입력 4

5 10
0 1 1
0 2 2
0 3 1
0 4 2
1 2 1
1 3 2
1 4 1
2 3 2
2 4 1
3 4 2

예제 출력 4

1 0 1 0 1 0 1 1 1 1

예제 입력 5

3 3
0 1 1
1 2 2
2 0 3

예제 출력 5

1 1 0