$N$개의 정점과, 가중치 있는 $M$개의 간선으로 이루어진 무향 그래프 $G$가 주어진다. $1$번 정점으로부터 $2, 3, ... , N$번 정점으로의 최단 경로를 모두 구해보자.

$G$는 다음을 만족한다.

• 어떤 정점 쌍을 골라도 둘을 잇는 경로는 반드시 존재한다.
• 자기 자신에게 향하는 간선은 존재하지 않는다.
• 어떤 두 정점을 직접적으로 잇는 간선은 두 개 이상 존재하지 않는다.

첫째 줄에 $N, M$이 공백으로 구분되어 주어진다. $(1 ≤ N ≤ 1,000; 1 ≤ M ≤ 100,000)$

둘째 줄부터 $M$개의 줄에 걸쳐 $u, v, w$가 공백으로 구분되어 주어진다. $(1 ≤ u, v ≤ N; 1 ≤ w ≤ 1,000)$ 이는 간선 하나가 정점 $u, v$를 가중치 $w$로 잇는다는 의미이다.