시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 1024 MB 22 5 5 23.810%

문제

$N$ 개의 정점과 $M$ 개의 간선이 있는 그래프가 있다. 각 간선에는 방향성이 있으며, 음이 아닌 정수 가중치를 가진다.

모든 $2 \le i \le N$ 에 대해서, 1번 정점에서 $i$ 번 정점으로 가는 두 개의 겹치지 않는 경로들 중, 비용 합의 최솟값을 계산하라. 경로가 겹치지 않는다는 것은, 같은 간선을 공유하지 않는다는 것이다. 경로의 비용은, 경로에 속하는 간선의 가중치를 전부 합한 값이다.

입력

첫 번째 줄에 테스트 케이스의 수 TC가 주어진다. 이후 TC개의 테스트 케이스가 새 줄로 구분되어 주어진다. 각 테스트 케이스는 다음과 같이 구성되었다.

  • 첫 번째 줄에 정수 $N, M$이 주어진다.
  • 이후 $M$ 개의 줄에 세 정수 $u_i, v_i, w_i$ 가 주어진다. $u_i$ 번 정점에서 $v_i$ 번 정점으로 가는 가중치 $w_i$ 의 간선이 존재한다는 뜻이다.

출력

각 테스트 케이스 마다 한 줄에 $N-1$ 개의 정수를 출력하라. 이 중 $i$ 번째 정수는, 1번 정점에서 $i+1$ 번 정점으로 가는 두 개의 겹치지 않는 경로들 중, 비용 합의 최솟값을 뜻한다. 만약 두 개의 겹치지 않는 경로가 존재하지 않는다면 -1을 출력하라.

제한

  • $1 \le u_i , v_i \le N$
  • $u_i \neq v_i$
  • $i \neq j \iff (u_i, v_i) \neq (u_j, v_j)$
  • $0 \le w_i \le 10^9$
  • 1번 정점에서 모든 정점으로 도달할 수 있다. 
  • 한 입력 파일에 대해, $N$ 의 합은 $100\,000$ 이하이다.
  • 한 입력 파일에 대해, $M$ 의 합은 $1\,000\,000$ 이하이다.

예제 입력 1

3
3 4
1 2 1
1 3 2
2 3 3
3 2 4
2 2
1 2 1
2 1 0
5 7
1 2 4
2 3 3
1 3 8
3 5 3
4 5 2
5 4 7
1 5 1

예제 출력 1

7 6
-1
-1 15 -1 11