Problem Description

There is an undirected graph with \( n \) vertices and \( m \) edges. Each edge \( i \) connects vertices \( A_i \) and \( B_i \) and has two costs: \( T_i \) and \( C_i \).

The cost to travel from vertex \( i \) to vertex \( j \) is the sum of \( T \) values multiplied by the sum of \( C \) values of the edges traversed.

The problem is to find, for each \( k \) (where \( 2 \le k \le n \)), the minimum cost to travel from vertex 1 to vertex \( k \).

Input Format

The first line contains two integers \( n \) and \( m \).

The next \( m \) lines each contain four positive integers \( A_i, B_i, T_i, C_i \), representing an edge connecting \( A_i \) and \( B_i \) with costs \( T_i \) and \( C_i \).

Output Format

Output \( n-1 \) lines, each containing a positive integer. The \( i \)-th line should represent the minimum cost to travel from city 1 to city \( i+1 \).

Notes/Hints

For 40% of the test cases, \( 1 \le n, m, T_i, C_i \le 100 \).

For 100% of the test cases, \( 1 \le n, m, T_i, C_i \le 2000 \) and \( 1 \le A_i, B_i \le n \).

Sample Explanation for the Second Test Case

To reach city 2, we choose the first road, which costs 1T and 7C, resulting in a cost of 7.

To reach city 3, we choose the second road, which costs 3T and 2C, resulting in a cost of 6.

To reach city 4, we choose roads 2, 4, and 5, which cost 11T and 4C, resulting in a cost of 44.

见题面 Input 部分

见题面 Output 部分