题目背景

临港区把城区道路分成了两类：一类是早年间铺下的干道，编号为 $0$；另一类是后来沿干道补出来的支线，编号为 $1$。两类道路都是单向通行的。

巡检队的骑手每天要跑一圈：从任意一个路口出发，先去程只走 $0$ 类干道，回程只走 $1$ 类支线，最后回到出发的那个路口。去程和回程都必须真的走出至少一条路。调度员想知道，这样一圈最少要跑多少距离。

题目描述

给定一张 $n$ 个点、$m$ 条有向弧的图。第 $i$ 条弧从 $u_i$ 指向 $v_i$，长度为 $w_i$（$w_i \ge 0$），颜色为 $c_i \in \{0, 1\}$。

一条巡逻走法是一条从某个顶点出发、沿着弧依次行走、最终回到该顶点的走法（顶点与弧都允许重复经过）。把这条走法经过的弧按经过顺序写成一列，就得到一串颜色。称这条走法是合规的，当且仅当可以选取走法的出发点，使得这串颜色形如

$$\underbrace{0\,0\,\cdots\,0}_{a \text{ 条},\, a \ge 1}\ \underbrace{1\,1\,\cdots\,1}_{b \text{ 条},\, b \ge 1}$$

也就是说：整条走法恰好由一段非空的 $0$ 色弧段和一段非空的 $1$ 色弧段接成，而且 $0$ 色在前、$1$ 色在后。

请求出一条合规走法的弧长总和的最小值。如果不存在任何合规走法，输出 -1。

输入格式

第一行两个整数 $n, m$。

接下来 $m$ 行，每行四个整数 $u_i, v_i, w_i, c_i$，描述第 $i$ 条弧。

输出格式

一行一个整数，表示合规走法弧长总和的最小值；若不存在这样的走法，输出 -1。

输入输出样例 #1

输入 #1

3 3
1 2 4 0
2 3 5 1
3 1 6 1

输出 #1

15

输入输出样例 #2

输入 #2

2 2
1 2 1 0
2 1 1 0

输出 #2

-1

输入输出样例 #3

输入 #3

4 4
1 2 1 0
2 1 1 0
2 3 1 1
3 2 1 1

输出 #3

4

说明

样例解释

样例 1：从 $1$ 号点出发，依次走 $1 \to 2$（$0$ 色，长 $4$）、$2 \to 3$（$1$ 色，长 $5$）、$3 \to 1$（$1$ 色，长 $6$），颜色序列是 $0,1,1$，符合要求，总长 $15$。图里只有一条 $0$ 色弧，去程非空就必须用它，因此这一圈无法更短。

样例 2：两条弧都是 $0$ 色，任何走法的颜色序列里都不会出现 $1$，故不存在合规走法。

样例 3：从 $2$ 号点出发，依次走 $2 \to 1$（$0$ 色，长 $1$）、$1 \to 2$（$0$ 色，长 $1$）、$2 \to 3$（$1$ 色，长 $1$）、$3 \to 2$（$1$ 色，长 $1$），颜色序列是 $0,0,1,1$，符合要求，总长 $4$；也只有在 $2$ 号点附近这两条弧上往返才能凑出这样的走法，故答案为 $4$。

数据范围

• 对于 $30\%$ 的数据，$1 \le n \le 10$，$1 \le m \le 50$；
• 对于 $60\%$ 的数据，$1 \le n \le 100$，$1 \le m \le 500$；
• 对于 $100\%$ 的数据，$1 \le n \le 400$，$1 \le m \le 2000$，$0 \le w_i \le 10^{9}$，$c_i \in \{0, 1\}$。

保证不存在 $u_i = v_i$ 的弧；两点之间可以有多条弧。若答案存在，答案不超过 $10^{12}$。