Improving Kitchener's Road Plan

As the new mayor of Kitchener, Alanna needs to reduce the annual maintenance cost of the city's road network while preserving the travel distances between intersections as in the current plan. The existing network is given as a collection of N intersections and M roads. The i-th road connects intersections u_i and v_i, has a length of l_i meters and costs c_i dollars per year to maintain.

In the current network, the shortest distance between any two intersections i and j is defined as the minimum total length over all paths connecting them; denote this distance as \( d(i,j) \). Alanna must choose a subset of roads with minimum total maintenance cost such that for any pair of intersections i and j that are connected in the original network (i.e. \( d(i,j) < \infty \)), the road subset contains some path whose total length is at most \( d(i,j) \>.

It can be shown that it is always optimal to choose only those roads which are candidates – that is, a road connecting intersections \( u \) and \( v \) with length \( l \) is a candidate if and only if \( l = d(u,v) \) (i.e. the road itself realizes the shortest distance between its endpoints in the full network). The problem then reduces to selecting a subset of candidate roads with minimum total cost such that the distance between any two intersections in the chosen subgraph is no more than \( d(i,j) \). (Note that even if a chosen road does not appear in some particular shortest path, some alternative route in the chosen subgraph must achieve the same distance.)

Task: Given the network description, compute the minimum annual maintenance cost of a road plan satisfying the distance‐preserving criteria.

inputFormat

The first line contains two integers \( N \) and \( M \) (1 \( \leq N \leq 100 \), 1 \( \leq M \leq 1000 \)), representing the number of intersections and roads respectively.

Each of the next \( M \) lines contains four integers \( u, v, l, c \) (1 \( \leq u,v \leq N \), 1 \( \leq l,c \leq 10^9 \)) indicating that there is a road between intersections \( u \) and \( v \) with length \( l \) meters and maintenance cost \( c \) dollars per year. The roads are bidirectional.

outputFormat

Output a single integer: the minimum total annual maintenance cost of a road plan that preserves the original travel distances. It is guaranteed that the original network is such that the distance \( d(i,j) \) between any two connected intersections is finite.

sample

3 3
1 2 3 10
2 3 3 10
1 3 6 5

20