#2389 포켓몬의 세계[part6. shortest Mr.C]

19  1 s   128 MB  

Description

4구역에는 존재해서는 안될 외쿸인 Mr.Y 가 있다. 외쿸인 Mr.Y는 그냥 보는 사람마다 막말을 해서, 사람들에게 상처를 준다. 어느날 갑자기 Mr.Y의 레이더망에 Mr.C가 걸려들었다. Mr.Y는 Mr.C를 보더니 "Hey Mr.C !! I don't see U" 그러자 Mr.C는 빡쳐서 "Yai E C Pak $\dots$ " 라고 말하고 싶었지만 소심해서 꾹 참고, 흥분을 가라앉히려고 노력을 했다. 그러다가 갑자기 아이디어가 번뜩 떠올라서, Mr.Y에게 이야기했다. "야 너는 대가리밖에 안보여 ! 너 대가리에서 니 발까지 최단경로 구해봐 baby" 사실 외쿸인 Mr.Y는 못알아 들은척을 했지만, 머릿속으로는 계산을 하고 싶었지만 그러하지 못하였다. 이런 Mr.Y를 도와주자.

Input

노드의 개수 $V ( 1 < V \leq 20000)$ 엣지의 개수 $E ( 1 < E \leq 300000)$ 엣지의 개수만큼의 $a_i, b_i, c_i$ $i (1 \leq i \leq E)$ a는 출발지, b는 도착지, c는 거리 $(1 \leq c_i \leq 100)$ 발의 번호는 $V$, 대가리의 번호는 $1$

Output

대가리부터 발까지의 최단경로를 구해라. 대가리가 너무커서 구할수가 없으면, "BIG HEAD"를 구할수가 있으면 최단 거리를 출력하라.

Sample Input

Sample Output

3 4
1 2 100
2 3 100
1 3 5
1 3 10
5

Source

wowoto9772