There are n urban areas and m bidirectional streets in the country. The streets in the nation structure an undirected weighted chart. The diagram isn't destined to be associated. Every street has it's own boundary w. You can go through the streets, however the public authority made another law: you can just go through two streets all at once (go from city a to city b and afterward from city b to city c) and you should pay (wab+wbc)2 cash to go through those streets. See if it
Correct answer will be upvoted else downvoted. Computer science.
There are n urban areas and m bidirectional streets in the country. The streets in the nation structure an undirected weighted chart. The diagram isn't destined to be associated. Every street has it's own boundary w. You can go through the streets, however the public authority made another law: you can just go through two streets all at once (go from city a to city b and afterward from city b to city c) and you should pay (wab+wbc)2 cash to go through those streets. See if it is feasible to go from city 1 to each and every other city t and what's the base measure of cash you really want to get from 1 to t.
Input
First line contains two integers n, m (2≤n≤105, 1≤m≤min(n⋅(n−1)2,2⋅105)).
Next m lines each contain three integers vi, ui, wi (1≤vi,ui≤n, 1≤wi≤50, ui≠vi). It's dependable that there are no numerous edges, for example for any edge (ui,vi) there could be no different edges (ui,vi) or (vi,ui).
Output
For each city t print one integer. In case there is no right way among 1 and t output −1. In any case print out the base measure of cash expected to venture out from 1 to t.
Step by step
Solved in 3 steps with 1 images
