Yuyuko

【题目背景】

幻想乡的亡灵公主，西行寺幽幽子，在幻想乡很受欢迎，经常有妖怪来拜访她，但是幽幽子并不喜欢被打扰，她希望从白玉楼出发，散步之后再回到白玉楼，同时路上遇到的妖怪越少越好(有趣的是道路两边的妖怪数量并不相同，分别从两个方向经过同一条道路遇到的妖怪数量是不同的)。当然，作为冥界的公主，她是不会重复经过同一条道路的。

【问题描述】

给定一个有 $n$ 个点$m$条无向边的图，每条无向边最多只能经过一次。

对于边$(u_i, v_i)$, 从 $u_i$ 到 $v_i$ 的代价为 $a_i$，从 $v_i$ 到 $u_i$ 的代价为 $b_i$，其中$a_i$和$b_i$不一定相等。

求一个包含 1 号点的有向环，使得环上代价之和最小。(保证图中没有重边和自环。)

【输入格式】

第一行两个个正整数 $n,m$，点数和边数。

接下来 $m$ 行，每行四个正整数，$u_i,v_i,a_i,b_i$。

从 $u_i$ 到 $v_i$ 的代价为 $a_i$，从 $v_i$ 到 $u_i$ 的代价为 $b_i$。

【输出格式】

输出一行，一个整数，如果有解输出最小代价，否则输出“-1”(不含引号)。

【输入样例1】

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

【输出样例1】

6

【输入样例2】

3 2
1 2 12 5
3 2 10 5

【输出样例2】

-1

【数据范围】

对于前 15% 的数据，$3 \leq n \leq 20, 3 \leq m \leq 20$；

对于前 30% 的数据，$3 \leq n \leq 150, 3 \leq m \leq 2500$；

对于前 70% 的数据，$3 \leq n \leq 5000, 3 \leq m \leq 10^4$；

对于100% 的数据，$3 \leq n \leq 3\times 10^4, 3 \leq m \leq 10^5,1\leq u_i, v_i \leq n，1 \leq a_i, b_i \leq 10^4$。

保证图中没有重边，即不存在 $i\neq j$，使得 $u_i = u_j，v_i = v_j$。

保证图中没有自环，即$u_i \neq v_i$。