406366: GYM102391 E Dead Cacti Society

Pet graphs are now a popular choice instead of animal pets in Korea. Among them, Trees are the most popular choice of pet graphs, due to their gentle properties and cute outlook. However, Koo is famous for being a maverick in this industry, because he only serves Cactus graphs to customers. Tree and Cactus are certain classes of graphs. A tree is a connected graph without cycles. A cactus is a connected graph, in which there exists no edge which belongs to two distinct cycles. Let's look at the example.

The graph in the first picture is both a tree and a cactus, the graph in the second picture is a cactus, and the graph in the final picture is neither of them. More cycles, more problems.

Koo had been serving Cactus graphs for 21 years with passion and love, but now he is old and tired. Although the popularity of pet graphs increased the visitors in his shop, they rarely became customers because most people considered Cactus graphs to be ugly for their pets. Koo's fortune is declining, and his life is getting tougher. In the end, Koo accepted the grim reality, and he decided to start a tree graph business - by cutting the edges of his lovely cacti.

A graph is a very sensitive creature, so cutting down the middle of the edge makes the whole graph decay. However, if you precisely cut the point where the vertex and the edge meet, the graph can heal itself. Thus, you should remove a whole edge, instead of cutting the middle. Also, you should never cut the graph to be disconnected: It's such a terrible thing to do to the graph.

If you cut the edge $$$e = \{u, v\}$$$, the vertices $$$u, v$$$ will be wounded. A cactus is such a tenacious creature, so it can immediately heal the wounded scars, growing a new edge and a new end vertex. Every edge and vertex has a nonnegative healing factor, which is known to Koo in advance. If an edge $$$e$$$ has a healing factor $$$RE_e$$$, and if an injured vertex $$$v$$$ has a healing factor $$$RV_v$$$, then a new edge of length $$$RE_e + RV_v$$$ will be created in each of the wounded vertices, along with a new vertex in the opposite side of the edge.

In the picture, the red edge is the edge we will cut, and the green edges are the newly created edges.

If we cut exactly one edge from each cycle of a cactus, we can create a tree. Generally, people prefer trees which has a small diameter, where the diameter of the tree is a maximum possible length of some shortest path between the two vertices in the tree. To make a lot of money, Koo wants to cut the cactus and minimize its diameter. Given a cactus, help Koo to find the minimum possible diameter that can be obtained by cutting the edges in the cycle.

In the first line, two integers $$$N, M$$$ are given, denoting the number of vertices and edges of the cactus. ($$$3 \le N \le 100\,000$$$, $$$N \le M \le 150\,000$$$). Every vertex is labeled with number $$$1, 2, \ldots, N$$$, and every edge is labeled with number $$$1, 2, \ldots, M$$$.

In the next line, $$$N$$$ integers $$$RV_1, RV_2, \ldots, RV_N$$$ are given, denoting the healing factor of each vertex. ($$$0 \le RV_i \le 10^9$$$).

In the next $$$M$$$ lines, four integers $$$A_i, B_i, L_i, RE_i$$$ are given in the $$$i$$$-th line. This indicates that the $$$i$$$-th edge is connecting two vertices $$$A_i, B_i$$$ with edge length $$$L_i$$$, and has healing factor $$$RE_i$$$. ($$$1 \le A_i, B_i \le N, A_i \neq B_i, 1 \le L_i, RE_i \le 10^9$$$)

It is guaranteed that the given graph is a cactus, and there are no distinct edges connecting the same pair of vertices.

Print a single integer denoting the answer.

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

10

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

22