Tenshi is given a connected undirected graph with \(n\) vertices \(m\) edges (weight of every edge is \(1\)) by Justin_CaO, and a total of \(k\) colors of stones, and **exactly one** stone (of one of \(k\) colors) at each vertex, the cost of transporting a stone from \(u\) to \(v\) is the shortest path length from \(u\) to \(v\).

Tenshi is busy with ICPC (International Carrot Placing Contest, prepared by FluffyBunny), so this graph is sent to you!

Your goal is to compute the **minimum cost** of transporting a stone of at least \(c\) colors to \(T\) for each vertex \(T\) (\(T=1, 2, \dots, n\)).