City C consists of n nodes, representing different places. There are m edges between these nodes. For

the edge ei = (ui , vi , wi), there is a bidirectional(undirected) trail connecting ui and vi with length of

wi .

For a path P = {pi}, consisting of edges p1, p2, p3, · · · , pk, the length of each edge is li = wpi . Normally,

passing the edge pi with length li will cost li units of energy. Specially, if li = K · li−1, then passing

this edge will only cost (K − 1) · li−1 units of energy.

Alice is starting from the node 1. Alice wants to know how many units of energy it will take at least

to visit the node x, for any x. If x is unreachable from the start point(node 1), you should output −1

as the result.