Module: Dijkstra의 알고리즘

Problem

주어진 꼭짓점에서 다른 모든 꼭지점까지의 변 길이가 음수가 아닌 무향 가중치 그래프에서 거리를 찾는 프로그램을 작성하세요. 큰 희소 그래프의 경우 프로그램이 빨라야 합니다.

입력

입력의 첫 번째 줄에는 숫자 NUM — Dijkstra 알고리즘의 다른 실행 수(다른 그래프에서). 그 다음에는 NUM개의 블록이 있으며 각 블록의 구조는 다음과 같습니다.

블록의 첫 번째 줄에는 공백 — 정점의 수와 그래프의 가장자리 수. 그 다음에는 M 행이 있으며 각 행에는 공백으로 구분된 3개의 정수가 포함되어 있습니다. 각각 0에서  N–1까지의 처음 두 개는 해당 에지의 끝을 나타내고 세 번째 — 범위는 0에서 20000까지이며 이 가장자리의 길이를 나타냅니다. 또한 블록의 마지막 줄에는 0에서  N–1 — 피크, 검색해야 하는 거리

하나의 테스트 NUM에서 서로 다른 그래프의 수는 5를 초과하지 않습니다. 꼭지점의 수는 60000을 초과하지 않습니다. 가장자리 — 200,000.

출판물

표준 출력(화면) NUM줄로 인쇄, 각 줄에는 N_i 공백으로 구분된 숫자 — 가중 무향 그래프의 지정된 시작 정점에서 0, 1, 2 등의 거리. 정점(마지막 숫자 뒤에 추가 공간이 허용됨). 일부 정점이 지정된 초기 정점에서 도달할 수 없는 경우 거리 대신 숫자 2009000999를 인쇄합니다(모든 실제 거리가 더 짧음을 보장함).

예