Problem Description

Given an undirected graph with \( N \) vertices numbered from \( 1 \) to \( N \), connected by \( M \) edges numbered from \( 1 \) to \( M \). Each edge connects vertices \( A_i \) and \( B_i \). These \( M \) edges are colored, with the color of the \( i \)-th edge being \( C_i \), where \( C_i \) is within the range \([1, M]\) and may not be distinct.

You are intelligent, and if I specify a color \( L \) that meets the following criteria:

• There exists an edge with color \( L \) that has one endpoint at your current location.
• There are no more than two edges with color \( L \) that have one endpoint at your current location.

You will move to the endpoint of that edge, otherwise, you will stay in place.

You are currently at vertex \( 1 \), and I want you to move to vertex \( N \). I can instruct you to follow certain colors, but the graph may not allow a path from \( 1 \) to \( N \). Therefore, I need to change some edge colors. Changing the color of the \( i \)-th edge to another number in the range \([1, M]\) costs \( P_i \). I want to know the minimum cost required to ensure you can successfully move to vertex \( N \).

Input Format

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

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

Output Format

A single integer representing the minimum cost, or \(-1\) if it is not possible to reach vertex \( N \).

Sample Input and Output

Sample Input #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

Sample Output #1

3

Sample Input #2

5 2
1 4 1 2
3 5 1 4

Sample Output #2

-1

Sample Input #3

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

Sample Output #3

1

Notes

Sample 1 Explanation

Operations can be performed as follows:

• Change the color of the 4th edge to 4, costing 1.
• Change the color of the 6th edge to 2, costing 2.

Total cost is 3, and then the following instructions can be given:

• Say "color 2!" to move from vertex 1 to vertex 2.
• Say "color 4!" to move from vertex 2 to vertex 4.

Sample 2 Explanation

Unfortunately, even with your intelligence, you cannot reach vertex \( N \).

Data Size and Constraints

This problem uses batched testing.

• 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 data, \( 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 duplicate edges.

Notes

Translated from The 20th Japanese Olympiad in Informatics Final Round D ロボット的英文翻译 Robot.

见题面 Input 部分

见题面 Output 部分