Minimum Energy Cost

You are given a directed weighted graph with n nodes and m edges. Each edge is represented by a tuple \((u,v,w,k)\) indicating an edge from node u to node v with weight w and a maximum allowed usage of k. When traversing an edge, you may decide to use it anywhere between 1 and \(k\) times consecutively. The cost of such a traversal is \(w \times x\), where \(x\) is the chosen number of uses.

Your task is to compute the minimum total energy cost required to travel from node 1 to node \(n\). If there is no valid path from the start to the destination, output \(-1\).

Note: All formulas are provided in \(\LaTeX\) format.

inputFormat

The input is read from standard input (stdin) and has the following format:

 n m
 u1 v1 w1 k1
 u2 v2 w2 k2
 ...
 um vm wm km

Where:

• n is the number of nodes.
• m is the number of edges.
• Each of the next m lines contains four integers \(u, v, w, k\) representing an edge from node u to node v with weight w and maximum usage \(k\).

outputFormat

Print a single integer to standard output (stdout): the minimum energy cost to reach node \(n\) from node 1. If there is no valid path, print \(-1\).

5 7
1 2 10 2
2 3 20 3
3 4 10 2
4 5 10 1
1 3 60 1
3 5 50 1
2 5 30 2

40