30346번 - 퍼텐셜 그래프 1 스페셜 저지

간선에 가중치가 있는 무향 단순 연결 그래프 $G = (V,\,E)$가 주어진다. $G$의 정점 위에서 정의되는 함수 $f: V \to \mathbb{R}$에 대해 함수 $g_f: V \to \mathbb{R}$를 다음과 같이 정의하자.

$$ g_f(u) = \sum_{v: \, (u,\,v) \in E} \big( f(u) - f(v) \big) \, \cdot \, w(u,\,v) $$

여기서 $\sum\limits_{v: \, (u,\,v) \in E}$ 는 $u$와 인접한 모든 정점 $v$에 대한 합을 나타내며, $w(u,\,v) = w(v,\,u) > 0$은 정점 $u$와 $v$를 잇는 간선 $(u,\,v) \in E$의 가중치이다.

$G$의 정점을 $1$에서 $N$까지의 정수라고 할 때, 다음 세 조건은 $f$와 $g_f$를 유일하게 결정한다.

• $f(1) = 1$이다.
• $f(N) = 0$이다.
• $1 < u < N$인 모든 정수 $u$에 대해 $g_f(u) = 0$이다.

그래프 $G$가 주어질 때 $g_f(1)$을 출력하는 프로그램을 작성하시오.

첫 번째 줄에 $G$의 정점 수 $N$과 간선 수 $M$이 공백으로 구분되어 주어진다. $\big( 2 \le N \le 100 ;$ $N-1 \le M \le \frac{N(N-1)}{2} \big)$

두 번째 줄부터 $M$개의 줄에 걸쳐 $G$의 간선의 정보를 나타내는 세 양의 정수 $u$, $v$, $w$가 공백으로 구분되어 주어진다. 이는 두 정점 $u$와 $v$를 잇는 간선이 존재하며 해당 간선의 가중치가 $w$임을 나타낸다. $\big( 1 \le u ,\, v \le N ;$ $u \neq v ;$ $1 \le w \le 100 \big)$

각 정점쌍을 잇는 간선은 최대 한 번만 주어진다.

$g_f(1)$의 값을 출력한다. 절대/상대 오차는 $10^{-6}$까지 허용한다.