퍼레이드

교차로 $N$개와 도로 $M$개로 이루어진 도시가 있다. 교차로에는 $0$번부터 $N-1$번까지, 도로에는 $0$번부터 $M-1$번까지 번호가 붙어 있다. 도로는 모두 양방향이고 서로 다른 두 교차로를 잇는다. 두 교차로를 잇는 도로는 많아야 하나다. 도시는 전부 이어져 있어서 어느 교차로에서든 도로를 따라 다른 교차로로 갈 수 있다.

시장은 도로 하나를 골라 그 도로에서 퍼레이드를 연다. 퍼레이드가 열리는 동안 그 도로는 지나갈 수 없다.

도시에는 교차로 쌍 $(X, Y)$마다 $X$와 $Y$를 오가는 버스 노선이 하나씩 있고, 노선은 모두 $N(N-1)/2$개다. 퍼레이드가 열리는 도로를 뺀 그래프에서 구한 $X$와 $Y$ 사이 최단 거리가 원래 최단 거리보다 길어지면 그 노선은 퍼레이드에 영향을 받는다. 퍼레이드 때문에 $X$에서 $Y$로 갈 수 없게 되는 경우도 영향을 받는 것으로 센다.

각 도로에서 퍼레이드를 열었을 때 영향을 받는 버스 노선이 몇 개인지 도로마다 구하는 프로그램을 작성하시오.

첫째 줄에 교차로의 개수 $N$ ($1 \le N \le 100$)과 도로의 개수 $M$ ($1 \le M \le 2000$)이 주어진다.

둘째 줄부터 $M$개 줄에 $0$번 도로부터 $M-1$번 도로까지 순서대로 도로의 정보가 주어진다. 각 줄에는 세 정수 from, to, time이 주어지며, from번 교차로와 to번 교차로를 오가는 데 time만큼 걸린다는 뜻이다. 두 교차로 번호는 $0$ 이상 $N-1$ 이하이고 서로 다르며, 걸리는 시간은 $1$ 이상 $1000$ 이하다.

$0$번 도로부터 $M-1$번 도로까지, 각 도로에서 퍼레이드가 열렸을 때 영향을 받는 버스 노선의 개수를 공백으로 구분해 한 줄에 출력한다.