#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/6/problems/G

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/6/problems/G

Repovive

Zero Distance - Repovive Premier Round 1 | Repovive | Repovive

Back

Code

Upload

Submissions

Learn

6G. Zero Distance

3500 ptstype :zen to enter zen mode

Time: 2sMemory: 256 MB

You are given a directed graph with $n$ vertices and $m$ directed edges.
Each directed edge $(u \to v)$ has an integer weight $w$ .

If you traverse an edge in its given direction $(u \to v)$ , the cost is $w$ .
If you traverse it in the opposite direction $(v \to u)$ , the cost is $-w$ .

For any walk, its cost is the sum of costs of its steps.

Define $dist(a,b)$ as the minimum possible cost among all walks from $a$ to $b$ .

We say the graph is good if it has no negative closed walk, meaning there is no walk that starts and ends at the same vertex with total cost $< 0$ .
Equivalently, the graph is good iff for every vertex $v$ , we have $dist(v,v)=0$ .

In one operation, you may choose one directed edge and do one of the following:

increase its weight by $1$
decrease its weight by $1$

Find the minimum number of operations needed to make the graph good.

Constraints:

$1 \le n \le 20$
$0 \le m \le 400$
$0 \le w \le 100$
$v \neq u$

Input

$n \quad m \\ u_1 \quad v_1 \quad w_1 \\ u_2 \quad v_2 \quad w_2 \\ \vdots \\ u_m \quad v_m \quad w_m$

Output

$\text{ans}$

Samples

Input

2 1
1 2 5

Explanation

No change is needed, so the minimum number of operations is $0$ .

Output

Input

Explanation

Set the weights to:

$(1 \to 2)=4$
$(2 \to 3)=5$
the two edges $(1 \to 3)$ both equal $9$

This needs $1$ operation on $(1 \to 2)$ , $1$ operation on $(2 \to 3)$ , and $1$ operation to change the edge $(1 \to 3)$ from $10$ to $9$ , so the total is $3$ .

Output

You are given a directed graph with $n$ vertices and $m$ directed edges.
Each directed edge $(u \to v)$ has an integer weight $w$ .

If you traverse an edge in its given direction $(u \to v)$ , the cost is $w$ .
If you traverse it in the opposite direction $(v \to u)$ , the cost is $-w$ .

For any walk, its cost is the sum of costs of its steps.

Define $dist(a,b)$ as the minimum possible cost among all walks from $a$ to $b$ .

In one operation, you may choose one directed edge and do one of the following:

increase its weight by $1$
decrease its weight by $1$

Find the minimum number of operations needed to make the graph good.

Constraints:

$1 \le n \le 20$
$0 \le m \le 400$
$0 \le w \le 100$
$v \neq u$

$n \quad m \\ u_1 \quad v_1 \quad w_1 \\ u_2 \quad v_2 \quad w_2 \\ \vdots \\ u_m \quad v_m \quad w_m$

No change is needed, so the minimum number of operations is $0$ .

Set the weights to:

$(1 \to 2)=4$
$(2 \to 3)=5$
the two edges $(1 \to 3)$ both equal $9$

This needs $1$ operation on $(1 \to 2)$ , $1$ operation on $(2 \to 3)$ , and $1$ operation to change the edge $(1 \to 3)$ from $10$ to $9$ , so the total is $3$ .