Compulsory Lanterns

Time limit: 3000 msMemory limit: 256 MB

A courier network has $N$ cities and $M$ directed roads. Each road has a positive length.

A route from city $1$ to city $x$ is eligible if its total length is as small as possible among all directed routes from city $1$ to city $x$ .

For a destination $x$ , a city $y$ is a compulsory lantern for $x$ if both of the following conditions hold:

$y \ne 1$ and $y \ne x$ .
Every eligible route from city $1$ to city passes through city .

City $i$ has lantern value $A_i$ . For every city $x$ , find the total value of all compulsory lanterns for $x$ . If city $x$ cannot be reached from city , this total is .

Input

The first line contains two integers $N$ and $M$ ( $1 \le N \le 2 \times 10^5$ , ), the number of cities and roads.

Output

Print one line containing $N$ integers $B_1, B_2, \ldots, B_N$ . For each with , must be the total value of all compulsory lanterns for city . Consecutive integers must be separated by one space.

Samples

Sample 1

Input

5 6
0 5 7 11 13
1 2 1
2 4 1
1 3 1
3 4 1
4 5 1
2 5 5

Output

0 0 0 0 11

For city $5$ , every eligible route passes through city $4$ . City $4$ is not compulsory for itself, and cities $2$ and $3$ are not compulsory for city $4$ because either one can be avoided by an eligible route.

Compulsory Lanterns

Input

Output

Samples

Sample 1

Submit

Submissions

Sample 2