Codeforces Round 816 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

divide and conquer

dp

geometry

graphs

greedy

shortest paths

*2400

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Long Way Home

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputStanley lives in a country that consists of $$$n$$$ cities (he lives in city $$$1$$$). There are bidirectional roads between some of the cities, and you know how long it takes to ride through each of them. Additionally, there is a flight between each pair of cities, the flight between cities $$$u$$$ and $$$v$$$ takes $$$(u - v)^2$$$ time.

Stanley is quite afraid of flying because of watching "Sully: Miracle on the Hudson" recently, so he can take at most $$$k$$$ flights. Stanley wants to know the minimum time of a journey to each of the $$$n$$$ cities from the city $$$1$$$.

Input

In the first line of input there are three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$2 \leq n \leq 10^{5}$$$, $$$1 \leq m \leq 10^{5}$$$, $$$1 \leq k \leq 20$$$) — the number of cities, the number of roads, and the maximal number of flights Stanley can take.

The following $$$m$$$ lines describe the roads. Each contains three integers $$$u$$$, $$$v$$$, $$$w$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$, $$$1 \leq w \leq 10^{9}$$$) — the cities the road connects and the time it takes to ride through. Note that some pairs of cities may be connected by more than one road.

Output

Print $$$n$$$ integers, $$$i$$$-th of which is equal to the minimum time of traveling to city $$$i$$$.

Examples

Input

3 1 2 1 3 1

Output

0 1 1

Input

4 3 1 1 2 3 2 4 5 3 4 7

Output

0 1 4 6

Input

2 1 1 2 1 893746473

Output

0 1

Input

5 5 2 2 1 33 1 5 93 5 3 48 2 3 21 4 2 1

Output

0 1 2 2 3

Note

In the first sample, it takes no time to get to city 1; to get to city 2 it is possible to use a flight between 1 and 2, which will take 1 unit of time; to city 3 you can get via a road from city 1, which will take 1 unit of time.

In the second sample, it also takes no time to get to city 1. To get to city 2 Stanley should use a flight between 1 and 2, which will take 1 unit of time. To get to city 3 Stanley can ride between cities 1 and 2, which will take 3 units of time, and then use a flight between 2 and 3. To get to city 4 Stanley should use a flight between 1 and 2, then take a ride from 2 to 4, which will take 5 units of time.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/20/2024 10:38:36 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|