Informatica Online Judge

  기지 방어(S) [1206 / 04B6]

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


The Champion of this Problem (C++) : gs15120 - 0ms / 2186byte
My Best Submission (C++) : N/A

[JKJeong 2015]

Background

경곽이는 GSHS마을에 살고 있다.

경곽이의 마을은 n개의 지점과 m개의 길로 구성되어 있다. 다음 그림은 7개의 지점과 11개의 길을 가지는 한 예이다.



항상 침략을 노리던 JKJeong는 경곽이의 기지를 함락시키기 위해 공격을 개시했다.

JKJeong는 1번 지점에서 공격을 시작하고, 경곽이의 기지는 n번 지점에 있다.

JKJeong장군은 항상 최단경로로 움직이기 때문에 최소한의 비용으로 경곽이의 기지까지 도달할 것이다.

주어진 예시의 경우는 다음과 같은 경로로 공격하게 되어 149초만에 경곽이의 기지가 함락당할 수 있다.



머리가 좋은 경곽이는 JKJeong장군의 공격을 완전히 막거나 아니면 최대한 늦추고 싶어한다.

경곽이가 할 수 있는 일은 오직 하나!! GSHS를 구성하는 길 중에 하나를 끊어서 이동할 수 없도록 만들 수 있다.

만약 길을 하나 끊어서 JKJeong장군이 침략할 수 없다면 작전은 성공이다. 하지만 항상 성공할 수 없다.

만약 성공할 수 없다면 다음 그림과 같이 3과 5를 연결하는 도로를 끊었다고 생각해보자.



그러면 JKJeong장군은 다음 그림과 같은 경로로 침략해 올 것이다. 이 때는 그래도 시간을 딜레이 하여 171초만에 기지가 함락 당할 것이다.



침략해 오는 JKJeong장군의 공격을 최선을 다해 막아보는 프로그램을 작성하시오.

Input

첫 번째 줄에 지점의 수 n과 길의 수 m이 공백으로 구분되어 입력된다.

다음 줄부터 m줄에 걸쳐서 연결되는 두 지점과 두 지점을 이동하는데 걸리는 시간이 공백으로 구분되어 입력된다.

[입력값의 정의역]
3 <= n <= 10
1 <= m <= 50
1 <= 이동 시간 <= 1,000

Output

첫 번째 줄에 원래 상태에서 침략당하는데 걸리는 시간에 "!"를 붙여서 출력한다.

만약 처음부터 침략이 불가능한 구조라면 "Impossible"(따옴표 제외)를 출력하고 종료한다.

침략을 당한다면 두 번째 줄에 경곽이가 최선을 다해서 한 길을 없앤 후의 결과를 출력한다.

만약 침략을 막을 방법이 있다면 "Success"를 출력한다.

그렇지 않다면 길을 하나 파괴한 후, 침략당하는데 걸리는 시간을 출력한다.

IO Example

입력
7 11
1 2 47
1 3 69
2 4 57
2 5 124
3 4 37
3 5 59
3 6 86
4 6 27
4 7 94
5 7 21
6 7 40

출력
149!
171

입력2
7 9
2 4 57
2 5 124
3 4 37
3 5 59
3 6 86
4 6 27
4 7 94
5 7 21
6 7 40

출력2
Impossible

입력3
7 9
1 2 47
1 3 69
2 4 57
2 5 124
3 4 37
3 5 59
3 6 86
4 6 27
5 7 21

출력3
149!
Success

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