Informatica Online Judge

  재수강 [2102 / 0836]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 3   Total Tried : 69


The Champion of this Problem (C++) : gs16106 - 40ms / 1709byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]
Writer ID : [gs16106]

Background

승한이는 이산구조 문제를 준비하면서 다음과 같은 Special Judge 문제를 내었다.

-가중치가 없는 그래프가 주어졌을 때, 1번 정점에서 n번 정점까지 가는 최단경로의 길이와 최단 경로를 출력하시오.-

하지만 김종혜 선생님께서 너무 풀기 쉬운 문제를 내었다고 승한이의 학점을 C+를 주셨다. 문제는 풀기 쉬웠지만 데이터를 만들고 Special Judge 세팅을 하느라 엄청난 고생을 했던 승한이는 억울해 했다.

결국 재수강을 한 승한이는 저번에 냈던 문제에서 각 간선에 색상을 부여하고, 여러 최단경로가 있을 때 생상의 수열이 사전순 최소인 것을 찾는 문제로 변형하여 Special Judge 세팅을 하는 고생을 하지 않는 문제를 출제하였다.

Input

첫 번째 줄에 정점의 수 n, 간선의 수 m이 주어진다. (2 ≤ n ≤ 100000, 1 ≤ m ≤ 200000)

이후 m개의 줄에 간선의 정보 ai, bi, ci가 주어진다. i번 간선이 ai 와 bi 정점을 양방향으로 이으며, 색상이 ci임을 뜻한다. (1 ≤ ai, bi ≤ n, 1 ≤ ci ≤ 10^9)

주어지는 입력에 대해서, 항상 1번 정점에서 n번 정점으로 가는 경로가 존재함이 보장된다.

Output

첫 번째 줄에 1번 정점에서 n번 정점으로 가는 최단 경로의 길이를 출력한다.

두 번째 줄에 l개의 정수를 공백으로 구분하여 출력한다. 최단 경로를 이루는 간선의 색을 순서대로 출력하면 된다.

최단 경로가 여럿 존재한다면, 이 수열이 사전순으로 최소인 최단 경로를 출력하라.

IO Example

입력1
3 3
1 2 1
2 3 1
1 3 1000

출력1
1
1000

입력2
4 6
1 2 1
1 3 2
3 4 3
2 3 1
2 4 4
3 1 1

출력2
2
1 3

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]