도시 사이를 이동하는 두 대의 차량이 있다. 한 대는 항상 일정한 속도로 이동하는 일반 차량이고, 다른 한 대는 부스터와 냉각 장치를 번갈아 사용하는 부스터 차량이다.

두 차량은 모두 \(1\)번 도시에서 동시에 출발한다. 두 도시를 연결하는 도로에 값 \(d\)가 주어졌을 때 각 차량이 그 도로를 통과하는 데 걸리는 시간은 다음과 같다.

• 일반 차량은 항상 \(2d\)의 시간이 걸린다.
• 부스터 차량은 부스터를 사용하는 동안 \(d\)의 시간이 걸린다.
• 부스터 차량은 냉각 운전을 하는 동안 \(4d\)의 시간이 걸린다.

부스터 차량은 첫 번째 도로에서 부스터를 사용한다. 이후 도로를 하나 통과할 때마다 부스터 사용과 냉각 운전을 번갈아 반복한다. 경로를 바꾸거나 이미 방문한 도시를 다시 방문하더라도 이 순서는 초기화되지 않는다.

두 차량은 각 도시까지 이동할 때 자신에게 걸리는 시간이 가장 짧은 경로를 선택한다. 따라서 두 차량이 선택하는 경로는 서로 다를 수 있다.

일반 차량이 부스터 차량보다 먼저 도착할 수 있는 도시의 수를 구하시오.

입력

첫째 줄에 도시의 수 \(N\)과 도로의 수 \(M\)이 공백으로 구분되어 주어진다.

다음 \(M\)개의 줄에 세 정수 \(a\), \(b\), \(d\)가 공백으로 구분되어 주어진다. 이는 도시 \(a\)와 도시 \(b\)를 연결하는 값이 \(d\)인 양방향 도로를 의미한다.

출력

일반 차량이 부스터 차량보다 먼저 도착할 수 있는 도시의 수를 출력한다.

제한 사항

• \(2 \le N \le 1,000\)
• \(N-1 \le M \le \min(100,000, N(N-1)/2)\)
• \(1 \le a, b \le N\)
• \(a \ne b\)
• \(1 \le d \le 100,000\)
• 주어진 그래프는 연결 그래프이다.
• 같은 두 도시를 연결하는 도로는 최대 하나만 주어진다.

예제 입력 1

5 6
1 2 3
1 3 2
2 3 2
2 4 4
3 5 4
4 5 3

예제 출력 1

1

예제 설명 1

각 도시까지 이동하는 데 필요한 최소 시간은 다음과 같다.

• \(1\)번 도시: 두 차량 모두 \(0\)
• \(2\)번 도시: 일반 차량은 \(6\), 부스터 차량은 \(3\)
• \(3\)번 도시: 일반 차량은 \(4\), 부스터 차량은 \(2\)
• \(4\)번 도시: 두 차량 모두 \(14\)
• \(5\)번 도시: 일반 차량은 \(12\), 부스터 차량은 \(15\)

두 차량의 도착 시간이 같은 \(4\)번 도시는 세지 않는다. 일반 차량이 부스터 차량보다 먼저 도착하는 도시는 \(5\)번 도시뿐이므로 정답은 \(1\)이다.