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}$까지 허용한다.

제한

힌트