35114번 - 웜홀

$N$개의 정점과 $M$개의 간선으로 구성된 단방향 그래프가 주어진다. 각 간선은 정수 가중치를 가진다. 정점 $u$에서 정점 $v$로 향하는 간선의 가중치가 $w$일 때, 이 간선을 $(u, v, w)$와 같이 표기하자. 간선 $(u, v, w)$를 이용해 정점 $u$에서 $v$로 이동하는 데에는 $w^2$만큼의 시간이 소요된다.

아래의 연산을 최대 한 번까지 수행할 수 있을 때, $1$번 정점에서 출발하여 $N$번 정점에 도착하는 데 걸리는 최단 시간을 구해보자.

1. 서로 다른 두 간선 $(x,y,a)$와 $(y,z,b)$를 삭제한다.
2. 간선 $(x,z,a-b)$를 추가한다.

첫 번째 줄에는 그래프의 정점의 수 $N$과 간선의 수 $M$이 주어진다. $(2\leq N\leq 300\,000;\ 1\leq M\leq 300\,000)$

두 번째 줄부터 $M$개의 줄에 걸쳐 간선에 대한 정보 $u,v,w$가 주어진다. 이는 $u$에서 $v$로 가는 가중치 $w$의 간선이 존재한다는 의미이다. $\left(u\neq v;\ -10^6\leq w \leq 10^6\right)$

주어진 그래프의 같은 정점 쌍 사이에 여러 개의 간선이 존재할 수 있으며, $1$번 정점에서 $N$번 정점으로 가는 경로가 반드시 존재함이 보장된다.

문제의 연산을 최대 한 번 적용하여 얻을 수 있는 그래프에서 $1$번 정점에서 출발해 $N$번 정점에 도착하는 최단 시간을 출력한다.