Source

My school hosted a local ICPC format contest yesterday, this problem appeared in it. Since it was for local only, I cannot provide link for submission (sorry!)

Statement

Given a weighted undirected graph $$$G$$$ with $$$n$$$ vertices and $$$m$$$ edges. Edge $$$e_i$$$ is a tuple $$$(u_i, v_i, A_i, B_i)$$$ denotes there is an edge connects $$$u_i$$$ with $$$v_i$$$, with cost $$$A_i$$$ and $$$B_i$$$. Consider path $$$u \rightarrow v$$$ is a sequence of edges $$$E: \{e_1, e_2,... e_k\}$$$, cost of $$$E$$$ is defined as product of (sum of all $$$A_x$$$) and (sum of all $$$B_x$$$) with $$$x$$$ is an edge in $$$E$$$. Calculate shortest path from node $$$1$$$ to all other nodes.

Sample Tests

Input 1

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

Output 1

8
3
14

Input 2

3 2
1 2 2 5
2 1 3 3

Output 2

9
-1