仙人掌图（Cactus graph）是一个连通的无向简单图，其中每条边最多属于一个简单环。

你有一个仙人掌图，每条边有两个非负整数权值 $a_i, b_i$。

你的目标是找到该仙人掌图的一棵生成树，使得 $(\sum a_i) \cdot (\sum b_i)$ 的值最小，其中求和是对生成树中包含的所有边进行的。

输入格式

第一行包含两个整数 $n, m$，表示仙人掌图的顶点数和边数。 $(1 \le n \le 50\,000, 0 \le m \le 250\,000)$

接下来的 $m$ 行，每行包含四个整数 $s, e, a_i, b_i$，表示第 $i$ 条边的两个端点及其权值。 $(1 \le s, e \le n, s \neq e, 0 \le a_i, b_i \le 50\,000)$

保证图是连通的，不包含自环或重边，且每条边最多属于一个简单环。

输出格式

输出一个整数：生成树中所有边的 $(\sum a_i) \cdot (\sum b_i)$ 的最小值。

样例

输入 1

3 3
1 2 0 1000
2 3 0 1000
3 1 1 1

输出 1

0