문제 설명
시열이는 졸업 작품으로 내비게이션을 만들려고 한다.
내비게이션에는 빅데이터와 인공지능, 알고리즘이 사용된다. 우선 차량에 설치된 내비게이션 프로그램이 몇 초마다 차량의 위치와 속도를 서버로 보낸다. 그러면 그를 바탕으로 실시간 통행량을 파악하고 수집된 정보를 바탕으로 교통 상황을 예측하는데, 이때 빅데이터와 인공지능이 사용된다. 최근 도로 상황을 보고 과거 상황 중 비슷한 패턴을 찾아 미래 상황을 예측하는 것이다.
인공지능을 이용한 빅데이터 분석 분야에서 세계 최고인 시열이는 각 도시를 연결하는 도로마다 도로의 길이, 신호등의 개수, 교통체증 등을 고려하여 통행시간을 예측해 정리했다. 하지만 완벽해 보이는 시열이도 알고리즘에는 약하기 때문에 게임 개발 분야의 전설인 환희에게 각 도시로 이동하는 가장 빠른 경로를 찾는 알고리즘을 만들어달라고 부탁했다. 환희는 게임 개발 일정 탓에 매우 바빴지만, 마음이 여려서 어쩔 수 없이 시열이의 부탁을 받아들였다.
경로는 어떤 도시에서 다른 도시로 이동할 때 거치는 도로의 집합이다. 시열이와 바쁜 환희를 위해 1번 도시에서 출발해서 각 도시로 이동하는 데 걸리는 최소 시간을 구해주자.
입력 설명
첫째 줄에 도시의 수 N (1 ≤ N ≤ 10,000)과 도로의 수 M (1 ≤ M ≤ 300,000)이 주어진다. 도시는 1부터 N까지 번호가 매겨져 있다. 둘째 줄부터 M개의 줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u, v, t)가 순서대로 주어진다. 이는 u번 도시에서 v번 도시로 가는데 시간이 t 소요되는 양방향 도로가 존재한다는 뜻이다. u와 v는 서로 다르며 d는 1,000 이하의 자연수이다.
출력 설명
첫째 줄부터 N개의 줄에 걸쳐, i번째 줄에 1번 도시에서 출발해서 i번 도시로 이동하는데 걸리는 최소 시간을 출력한다. 1번 도시 자신은 0을 출력하고, 경로가 없는 경우 -1을 출력한다.
입력 예시 Copy
4 6
3 4 4
1 2 3
1 3 7
2 3 1
2 4 8
1 4 10
출력 예시 Copy
0
3
4
8