# UOJ003 - Magic Forest

Submit Your Solution (opens new window)


This problem is from NOI 2014.

# Description

You want to visit a hermit living in the Magic Forest. The forest can be seen as an undirected graph which has nn (2≤n≤5×1042\leq n\leq5\times10^4) nodes and mm (0≤m≤1050\leq m\leq10^5) edges. Initially, you are at node 11 while the hermit lives at node nn.

There are some monsters living in the Magic Forest, too. When someone passes an edge, the monsters will attack him. Luckily, you can take some guarding sprites with you when you depart. There are two types of sprites, type-A and type-B, and you can take as many as you want.

Every edge eie_i has two values aia_i and bib_i, which means that you need at least aia_i type-A sprites and bib_i type-B sprites to pass this edge. What is the minimal number of sprites you will need to take, if you choose the route optimally?

# Input

  • The first line contains two integers, the number of nodes nn, and the number of edges mm.
  • The following mm lines each contain four integers xi,yi,ai,bix_i,y_i,a_i,b_i, describing an undirected edge between xix_i and yiy_i, which requires at least aia_i type-A sprites and at least bib_i type-B sprites.

Note that there might be multiple edges and self loops.

# Output

One integer, the minimal number of sprites required to visit the hermit. If you can never reach the hermit, output −1-1 instead.

# Samples

# Input 1

4 5
1 2 19 1
2 3 8 12
2 4 12 15
1 3 17 8
3 4 1 17

# Output 1


# Sample Explanation

  • Choosing 1→2→41\rightarrow2\rightarrow4 requires 19+15=3419+15=34 sprites.
  • Choosing 1→3→41\rightarrow3\rightarrow4 requires 17+17=3417+17=34 sprites.
  • Choosing 1→2→3→41\rightarrow2\rightarrow3\rightarrow4 requires 19+17=3619+17=36 sprites.
  • Choosing 1→3→2→41\rightarrow3\rightarrow2\rightarrow4 requires 17+15=3217+15=32 sprites.

So at least 3232 sprites are needed.

# Tutorial