Description

Given an undirected graph with $N$ vertices numbered $1 \sim N$, connected by $M$ edges numbered $1 \sim M$. Edge $i$ connects vertices $A_i$ and $B_i$. Each edge is painted with a color: the color of edge $i$ is $C_i$. It is guaranteed that $C_i \in [1,M]$, but the values $C_i$ are not necessarily distinct.

You are very smart. If I say a color $L$ and it satisfies the following conditions:

• There exists an edge with color $L$ such that one of its endpoints is the vertex where you are currently located.
• There do not exist two or more edges with color $L$ such that one of their endpoints is the vertex where you are currently located.

then you will move along that edge to the other endpoint. Otherwise, you will stay where you are.

You are currently at vertex $1$. I want you to move to vertex $N$. I can tell you some colors, and you will move according to those colors. However, this graph may not allow you to go from $1$ to $N$, so I want to change the colors of some edges. Changing the color of edge $i$ to another number in $[1,M]$ costs $P_i$. Find the minimum total cost needed to make it possible for you to successfully reach vertex $N$.

Input Format

The first line contains two integers $N,M$, representing the number of vertices and the number of edges in the undirected graph.

The next $M$ lines each contain four integers $A_i,B_i,C_i,P_i$, describing an edge.

Output Format

Output one integer, the minimum total cost. If it is impossible to reach, output $-1$.

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

3

5 2
1 4 1 2
3 5 1 4

-1

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

1

Hint

Explanation for Sample 1

I can do the following operations:

• Change the color of edge $4$ to $4$, with cost $1$.
• Change the color of edge $6$ to $2$, with cost $2$.

The total cost is $3$, and then I can command you as follows:

• I say “color $2$!”. You move from vertex $1$ to vertex $2$.
• I say “color $4$!”. You move from vertex $2$ to vertex $4$.

Explanation for Sample 2

Unfortunately, even if you are this smart, you still cannot reach vertex $N$.

Constraints

This problem uses bundled testdata.

• Subtask 1 (34 pts): $N \le 1000$, $M \le 2000$.
• Subtask 2 (24 pts): $P_i=1$.
• Subtask 3 (42 pts): no additional constraints.

For $100\%$ of the testdata, $2 \le N \le 10^5$, $1 \le M \le 2 \times 10^5$, $1 \le A_i<B_i \le N$, $1 \le C_i \le M$, $1 \le P_i \le 10^9$, and the graph has no multiple edges.

Notes

Translated from The 20th Japanese Olympiad in Informatics Final Round D ロボット English translation Robot.

Translated by ChatGPT 5