National Olympiad in Informatics, China, 2014
To obtain the master calligrapher's true teachings, little E has decided
to pay a visit to the hermit of an enchanted forest. The forest can be
represented as an undirected graph with nodes and
edges. The
nodes are numbered
and the edges are numbered
. Initially, little E is located at node
, and the hermit is
living at node
. In order to meet the hermit, little E must first
travel through this enchanted forest.
The forest is home to many goblins. Whenever a human travels along an
edge, the goblins on this edge will strike. Fortunately, node is home
to two types of elven protectors: type A elves and type B elves. Little
E can harness their powers to help him reach his goal.
As long as little E brings along enough protector elves, the goblins
will not launch their attacks against him. Generally speaking, each edge
of the undirected graph is associated with two values
and
. If the number of type A elves that little E is bringing is
no less than
, and if the number of type B elves that little E is
bringing is no less than
, then the goblins will not attack him
along this edge of the forest. If and only if little E remains
unattacked on every edge that he travels through, then his journey to
find the hermit will be considered successful.
Since bringing along protector elves is a big burden, little E would like to know the minimum total number of elves he could bring along and still successfully reach the hermit. The total number of elves is equal to the sum of the number of type A elves and the number of type B elves.
Input Specification
The first line of input will contain two integers and
representing
the number of nodes and edges in the undirected graph.
For the next lines, line
will contain 4 space-separated
positive integers
,
,
, and
, indicating
that the
-th edge runs between nodes
and
. The
meanings of
and
are as explained above.
Output Specification
Output a single integer: if little E can successfully reach the hermit,
then output the minimum number of total elves that he will have to bring
along. Otherwise, if little E cannot successfully reach the hermit, then
output -1
.
Sample Input 1
4 5
1 2 19 1
2 3 8 12
2 4 12 15
1 3 17 8
3 4 1 17
Sample Output 1
32
Explanation 1
If little E takes the path , he will require
protector elves.
If little E takes the path , he will require
protector elves.
If little E takes the path , he will require
protector elves.
If little E takes the path , he will require
protector elves.
Overall, little E will require a minimum of protector elves.
Sample Input 2
3 1
1 2 1 1
Sample Output 2
-1
Explanation 2
Little E has no way of reaching node from node
. Thus, we output
-1
.
Constraints
Test Case | |||
---|---|---|---|
Problem translated to English by .
Comments