Optimal Bus Route Disruption

Cocoa and Kaka live in the east suburb of HF City. Every day they must take several buses to reach their school located near the west side of the city. One day, after participating in an Olympiad in Informatics, they discovered that the bus routes they take every morning might not be optimal.

Cocoa reasons: "It is very likely that we waste a lot of time on our way to school. Let’s write a program to compute the minimum time needed to get to school!"

In HF City there are a total of \(N\) bus stops, numbered from 1 to \(N\). Assume that Cocoa and Kaka live near bus stop 1, and their school is near bus stop \(N\). The city operates \(M\) bidirectional bus routes. The \(i\)th bus route runs directly between stops \(p_i\) and \(q_i\) and takes \(t_i\) time to travel. Each route also has an associated cost \(c_i\) for being removed from the available routes. A higher \(c_i\) means it is easier for Kaka to notice the prank.

Initially, both compute the actual minimum time \(d_0\) needed to go from bus stop 1 to bus stop \(N\) using all available routes. Cocoa now plans a prank: he wants to remove some bus routes such that the new minimum travel time (after the removals) becomes strictly greater than \(d_0\). However, he wishes to make the sum of the removal costs \(c_i\) as small as possible so as not to raise suspicion.

Your task is to write a program that:

1. Reads the bus route information from the input;
2. Computes the actual minimum travel time \(d_0\) from stop 1 to stop \(N\);
3. Determines a set of bus routes to remove so that, after removal, every path from bus stop 1 to \(N\) with a total travel time equal to \(d_0\) is disrupted, and the sum of removal costs is minimized.
4. Outputs the values \(d_0\) and the minimum total removal cost.

Note: An edge (bus route) is considered to be on a shortest path if either \(d(1, u) + t + d(v, N) = d_0\) or \(d(1, v) + t + d(u, N) = d_0\) (using \(t\) for travel time) where \(d(1, u)\) is the shortest distance from node 1 to node \(u\), and \(d(v, N)\) is the shortest distance from node \(v\) to node \(N\). The disruption is achieved by “cutting” all shortest paths (i.e. removing at least one edge from every shortest path), and the goal is to minimize the sum of the removal costs \(c_i\) among those edges.

inputFormat

The first line contains two integers \(N\) and \(M\) (\(2 \leq N \leq 10^5\), \(1 \leq M \leq 10^5\)), representing the number of bus stops and bus routes, respectively.

Then \(M\) lines follow, each containing four integers \(p_i\), \(q_i\), \(t_i\), and \(c_i\) (\(1 \leq p_i, q_i \leq N\); \(1 \leq t_i \leq 10^9\); \(1 \leq c_i \leq 10^9\)). Each line describes a bidirectional bus route between stops \(p_i\) and \(q_i\) that takes \(t_i\) time and has a removal cost of \(c_i\).

outputFormat

Output two integers separated by a space: the actual minimum travel time \(d_0\) and the minimum total removal cost required to disrupt every shortest path (so that the new minimum travel time becomes strictly greater than \(d_0\)).

sample

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

2 2