“宠物图”现在是韩国除了动物宠物之外的一种流行选择。其中，树因其温和的性质和可爱的外观，成为了最受欢迎的宠物图。然而，Koo 在这个行业中以特立独行而闻名，因为他只向顾客提供仙人掌图（Cactus graphs）。树和仙人掌是图论中的特定类别。树是指没有环的连通图。仙人掌图是指其中不存在任何一条边属于两个不同环的连通图。让我们看一看示例。

第一张图既是树也是仙人掌，第二张图是仙人掌，最后一张图既不是树也不是仙人掌。环越多，问题越多。

Koo 怀着热情和爱心经营仙人掌图生意已经 21 年了，但现在他老了，也累了。尽管宠物图的流行增加了他店里的访客，但他们很少成为顾客，因为大多数人认为仙人掌图作为宠物来说太丑了。Koo 的财富正在缩水，生活也变得越来越艰难。最终，Koo 接受了严酷的现实，他决定开始经营树图生意——通过切割他心爱的仙人掌的边。

图是一种非常敏感的生物，直接从边的中间切断会导致整个图衰变。然而，如果你精确地切断顶点与边相连的点，图就可以自我修复。因此，你应该移除整条边，而不是从中间切断。此外，你绝不能将图切成不连通的状态：这对图来说是一件非常糟糕的事情。

如果你切断边 $e = \{u, v\}$，顶点 $u, v$ 将会受伤。仙人掌是一种生命力顽强的生物，它可以立即治愈伤口，长出一条新边和一个新的端点。每条边和每个顶点都有一个非负的治愈因子，Koo 事先已知这些数值。如果边 $e$ 的治愈因子为 $RE_e$，且受伤的顶点 $v$ 的治愈因子为 $RV_v$，那么在每个受伤的顶点处都会产生一条长度为 $RE_e + RV_v$ 的新边，并在边的另一侧产生一个新的顶点。

在图中，红色的边是我们即将切断的边，绿色的边是新产生的边。

如果我们从仙人掌的每个环中恰好切断一条边，我们就可以得到一棵树。通常，人们更喜欢直径较小的树，其中树的直径是指树中任意两点间最短路径的最大可能长度。为了赚更多的钱，Koo 想要通过切割仙人掌的边来最小化其直径。给定一个仙人掌，请帮助 Koo 找到通过切割环中的边所能获得的最小直径。

输入格式

第一行包含两个整数 $N, M$，表示仙人掌的顶点数和边数 ($3 \le N \le 100\,000, N \le M \le 150\,000$)。每个顶点的编号为 $1, 2, \dots, N$，每条边的编号为 $1, 2, \dots, M$。

下一行包含 $N$ 个整数 $RV_1, RV_2, \dots, RV_N$，表示每个顶点的治愈因子 ($0 \le RV_i \le 10^9$)。

接下来的 $M$ 行中，第 $i$ 行包含四个整数 $A_i, B_i, L_i, RE_i$。这表示第 $i$ 条边连接两个顶点 $A_i, B_i$，边长为 $L_i$，治愈因子为 $RE_i$ ($1 \le A_i, B_i \le N, A_i \neq B_i, 1 \le L_i, RE_i \le 10^9$)。

保证给定的图是一个仙人掌，且不存在连接同一对顶点的不同边。

输出格式

输出一个整数，表示答案。

样例

样例输入 1

3 3
1 2 3
3 1 2 3
1 2 1 2
2 3 3 1

样例输出 1

10

样例输入 2

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

样例输出 2

22

Figure 1. Examples of a tree, a cactus graph, and a graph that is neither.