Cave Exploration

Below World Mountain there is a cave entrance, and the entrance leads directly to room 1, where the exploration starts. Inside the cave are several small rooms connected by tunnels. Tunnels do not cross each other, and at most one tunnel connects the same pair of rooms.

The cave exploration race starts in room 1, moves through the cave, and then returns to room 1 to exit. A participant may choose any route, but all of the following rules must be satisfied.

• At least one room other than room 1 must be visited.
• No room other than room 1 may be visited more than once.
• No tunnel may be used more than once.

Room 1 is visited once at the start and once at the end, so it is the only exception.

The time needed to pass through a tunnel may depend on the direction. Ignore the time between the cave entrance and room 1, and ignore any time spent moving inside a room. Find the minimum total travel time among all valid routes.

The first line contains n, the number of rooms, and m, the number of tunnels. (3 <= n <= 5000, 3 <= m <= 10000)

Each of the next m lines contains four integers a b c d describing one tunnel. Moving from room a to room b takes time c, while moving from room b to room a takes time d. (1 <= a, b <= n, a != b, 1 <= c, d <= 10000)

The rooms are numbered from 1 to n, and room 1 is the starting room. It is guaranteed that at least one valid route exists.

Print the minimum time required to complete the cave exploration.