Unique‐Color Graph Traversal

You are given an undirected graph with N vertices (numbered from 1 to N) and M edges (numbered from 1 to M). Each edge connects two vertices and has an associated color and a cost. The i‑th edge connects vertices A_i and B_i and its color is C_i (an integer in the range \( [1,M] \)) and it has a cost \(P_i\) used for modifying its color.

The problem is as follows. You are to instruct a very intelligent traveler who, starting at vertex 1, will obey your commands to eventually reach vertex N. The traveler’s movement rule is as follows. When you announce a color \(L\) at his current vertex \(u\), if and only if:

• There is at least one edge incident to \(u\) with final color \(L\), and
• There is exactly one edge incident to \(u\) with final color \(L\),

then the traveler moves along that unique edge (to the other endpoint). If the condition is not met he stays in place.

You are allowed to change the color of any edge. Changing the color of the i‑th edge (to any other color in \([1,M]\)) incurs a cost of \(P_i\). In order for you to be able to guide the traveler from 1 to N by announcing a sequence of colors, you must change some edge colors so that on some simple path \(P=1\to v_2 \to \cdots \to N\rangle</em> the following holds:

• For every vertex \(u\) on the path except \(N\), you plan to use a particular incident edge (say, \(e\)) to leave \(u\). You will announce the final color on that edge.
• At vertex \(u\) the "unique edge" condition must hold – that is, among all edges incident to \(u\) the edge you wish to travel on must be the only one whose final color equals the announced color.

You have two methods for ensuring uniqueness at a vertex \(u\) (where the chosen outgoing edge is \(e\), with original color \(C(e)\)):

1. Keep the original color. In this case the outgoing edge \(e\) remains with color \(C(e)\) (at no cost) but then every other edge incident to \(u</em> that originally has color \(C(e)\) becomes a conflict – you must change each such edge’s color at its modification cost. Let
   \(\text{cost}_{\rm keep}(u,e)=\begin{cases}\;0,&\text{if no other edge at } u \text{ has color } C(e),\\ \;\Bigl(\sum_{\substack{f\;\in\;\nabla(u)\\ f\neq e \;\wedge\; C(f)=C(e)} }P(f)\Bigr),&\text{otherwise.}\end{cases}\)</p>
2. Change the chosen edge’s color. You may alter the color of \(e\) (at a cost \(P(e)\)) and choose a new color which does not appear on any other edge incident to \(u</em> (this is possible provided that not all colors \(1,2,\ldots,M\) appear among the other edges at \(u\)). In this option no other edge at \(u\) needs to be modified. That is, \(\text{cost}_{\rm change}(u,e)=P(e)\) if a fresh color is available; otherwise this option cannot be used.

Your task is to choose a simple path from 1 to N and for each vertex (except N) decide, for the edge you use, whether to keep its original color and fix all conflicts or change its color to a fresh one – so that the traveler will always have a unique outgoing edge when you announce the corresponding color. The total cost is the sum over the vertices on the path of the cost incurred at that vertex. (Note that if an edge not on the chosen path is modified to resolve a conflict at one vertex and it causes a conflict at another vertex on the chosen path, a single modification may serve both – however, for our problem you may assume that a strategy based solely on independently fixing each vertex is acceptable.)

Find the minimum total cost needed so that there exists a color‐announcement strategy that guides the traveler from vertex 1 to vertex N.

Note: In the input, each edge is described by four integers: A_i, B_i, C_i, and P_i. The final answer is guaranteed to be achievable by, for example, for every vertex making the safe choice of changing the color on the outgoing edge when necessary. One valid (though not always optimum) strategy is to always use the change option (if available) at every vertex, which leads to a total cost equal to the sum of the \(P(e)\) values along a simple path from 1 to N. Optimizing between the two methods may sometimes lead to a lower total cost.

inputFormat

The first line of input contains two integers N and M (2 ≤ N ≤ 10⁵, 1 ≤ M ≤ 10⁵), the number of vertices and edges respectively.

Then M lines follow. The i‑th of these lines contains four integers A_i, B_i, C_i and P_i (1 ≤ A_i, B_i ≤ N, 1 ≤ C_i ≤ M, 0 ≤ P_i ≤ 10⁹), describing an edge between vertices A_i and B_i with color C_i and modification cost P_i.

It is not guaranteed that the original graph (without modifications) allows a path from vertex 1 to vertex N following the traveler’s rule.

outputFormat

Output a single integer – the minimum total cost required to change edge colors so that there exists a sequence of color announcements that guides the traveler from vertex 1 to vertex N.

sample

3 3
1 2 1 5
2 3 1 3
1 3 2 10

0