Cheapest Travel in Byteotia

In Byteotia there are \(n\) towns and \(m\) bidirectional railway connections operated by Byteotian State Railways (BSR). Each direct railway connection costs \(a\) bythalers. Byteotian Airlines (BA) now plans to offer flights between certain pairs of towns that are not directly connected by rail. A flight is available between two towns if and only if the cheapest railway route between them uses exactly two segments (i.e. one change). Each flight ticket costs \(b\) bythalers.

A route is defined as a sequence of one or more direct connections, where each connection can be either a railway ride or an airplane flight. Your task is to compute the minimum cost of travelling between every pair of towns.

Note: All connections (both railway and flight) are bidirectional. In cases where a pair of towns is not reachable by any sequence of connections, output -1 as the cost.

inputFormat

The first line of input contains four integers \(n\), \(m\), \(a\) and \(b\) (number of towns, number of railway segments, cost of a railway ticket and cost of a flight ticket respectively).

Each of the next \(m\) lines contains two integers \(u\) and \(v\) indicating that towns \(u\) and \(v\) are directly connected by railway. The towns are numbered from 1 to \(n\>.

outputFormat

Output an \(n \times n\) matrix, where the \(j\)-th number in the \(i\)-th line is the minimum cost of travelling between town \(i\) and town \(j\). For the same town, output 0. If a town cannot be reached, output -1 in its place. Separate numbers with a single space.

sample

3 2 10 5
1 2
2 3

0 10 5
10 0 10
5 10 0