두 최단 경로

정점이 $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$ 이하이다.