두 최단 경로

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