문제 설명

라이언 타운으로 가기 전에 라이캣은 여러 부족에게 편지를 보내 함께 일어서자고 부탁하기로 했습니다. 개굴 마을, JAVA 마을, 당근 마을처럼 부족마다 쓰는 말이 달라서 편지를 번역해야 합니다.
"고양이어로 쓴 편지가 모든 부족에게 제대로 닿아야 한다냥."
"번역기를 여러 번 거치면 뜻이 조금씩 틀어진다 개굴. 손실이 가장 적은 길로 보내야 한다 개굴!"
대리인 No.1이 만든 번역기들이 있습니다. 번역기 하나는 한 언어에서 다른 한 언어로, 한 방향으로만 번역하고, 번역기마다 '정확도 손실'이 정해져 있습니다. 편지가 번역기를 여러 번 거치면 손실은 모두 더해집니다.
언어는 0번부터 n-1번까지 있고, 0번이 라이캣이 쓰는 고양이어입니다. 언어 수 n과 번역기 목록 translators가 주어질 때, 고양이어 편지를 각 언어로 옮길 때 생기는 손실 합의 최솟값을 0번 언어부터 차례로 리스트에 담아 반환하세요.
- 0번 언어(고양이어)의 값은 0입니다.
- 어떤 번역기를 어떻게 거쳐도 옮길 수 없는 언어는 -1입니다.
제한 사항
- 입력은
[n, translators]형태입니다. - 1 ≤
n≤ 10,000 - 0 ≤
translators의 길이 ≤ 50,000 - 원소
[a, b, loss]는 a번 언어를 b번 언어로 옮기는 번역기이고, 정확도 손실이 loss라는 뜻입니다. 거꾸로(b → a)는 옮기지 못합니다. - 0 ≤ a, b ≤ n - 1, a ≠ b, 0 ≤ loss ≤ 100 (모두 정수)
- 같은 두 언어 사이에 번역기가 여러 개 있을 수 있습니다.
입출력 예
| 입력 | 출력 |
|---|---|
| [4, [[0, 1, 5], [0, 2, 1], [2, 1, 2], [1, 3, 1], [2, 3, 7]]] | [0, 3, 1, 4] |
| [3, [[1, 0, 2], [0, 1, 4]]] | [0, 4, -1] |
| [5, [[0, 1, 0], [1, 2, 0], [2, 3, 10], [0, 3, 9], [3, 4, 1], [4, 3, 0]]] | [0, 0, 0, 9, 10] |
입출력 설명
첫 번째 예
0번은 고양이어, 1번은 개굴어, 2번은 JAVA어, 3번은 당근어라고 해 봅시다.
- 개굴어(1번): 바로 옮기면 손실 5, JAVA어를 거치면 1 + 2 = 3이므로 3입니다.
- JAVA어(2번): 바로 옮기면 손실 1입니다.
- 당근어(3번): 고양이어 → JAVA어 → 개굴어 → 당근어로 옮기면 1 + 2 + 1 = 4입니다. JAVA어에서 바로 옮기면 1 + 7 = 8이라 더 큽니다.
두 번째 예
1번 → 0번 번역기는 0번 → 1번으로 쓸 수 없습니다. 1번 언어는 0번 → 1번 번역기로 옮겨 4입니다. 2번 언어로 옮기는 번역기는 없으므로 -1입니다.
세 번째 예
손실이 0인 번역기도 있습니다. 3번 언어는 2번을 거치면 10, 바로 옮기면 9이므로 9이고, 4번 언어는 3번을 거쳐 9 + 1 = 10입니다.
예시 테스트
| # | 입력 | 기대값 |
|---|---|---|
| 1 | [4, [[0, 1, 5], [0, 2, 1], [2, 1, 2], [1, 3, 1], [2, 3, 7]]] | [0, 3, 1, 4] |
| 2 | [3, [[1, 0, 2], [0, 1, 4]]] | [0, 4, -1] |
| 3 | [5, [[0, 1, 0], [1, 2, 0], [2, 3, 10], [0, 3, 9], [3, 4, 1], [4, 3, 0]]] | [0, 0, 0, 9, 10] |
입력은 solution에 넘기는 인자예요. 제출하면 숨김 테스트 12개도 함께 채점해요.