합리적인 이동 경로

무방향 가중치 그래프에서 정점 1에서 정점 2로 이동하려고 한다.

어떤 정점이 정점 2에 더 가깝다는 것은, 그 정점에서 정점 2까지의 최단 거리가 더 짧다는 뜻이다. 이동할 때마다 현재 정점보다 정점 2에 더 가까운 정점으로만 이동하는 경로를 합리적인 이동 경로라고 한다. 이런 경로가 전체 최단 경로일 필요는 없다.

그래프가 주어졌을 때 가능한 합리적인 이동 경로의 개수를 구하라.

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다.

• 1 < N <= 1,000
• 1 <= M <= 100,000

다음 M개의 줄에는 각 간선을 나타내는 세 정수 A, B, C가 주어진다. 이는 정점 A와 정점 B가 길이 C인 간선으로 연결되어 있음을 뜻한다.

• 0 < C <= 10,000
• 두 정점 사이에는 간선이 최대 하나만 존재한다.
• 모든 간선은 방향이 없다.

합리적인 이동 경로의 개수를 첫째 줄에 출력한다.

답은 2147483647을 넘지 않는다.