1번 ~ N번까지 N개의 도시가 있고, 지호는 1번 도시에 살고 있다.

각 도시를 잇는 양방향 도로가 M개 있고, 각 도로를 통과하는데 걸리는 시간도 주어져 있다.

지호는 도로를 통과하지 않고, 텔레포트를 할 수 있다.

A 번 도시에서 B 번 도시로 텔레포트를 하면, ( A - B )를 제곱한 만큼 의 시간이 걸린다.

예를 들어, 3번 도시에서 7번 도시로 텔레포트를 하는 데에는 ( 3 - 7 )² = 16 의 시간이 걸린다.

텔레포트는 무한히 할 수 없고, 최대 P 번까지만 가능하다.

이 상황에서, 지호가 살고 있는 1번 도시로부터,

각 도시까지 가는 데 걸리는 최단 시간을 모두 구해보자.

제곱 텔레포트 timer 3s memory 256MB

제곱 텔레포트 3s 256MB