n cities numbered from 1 to n. Roads are two-way: roads[i] = [a, b, cost] is a road between cities a and b that costs cost to travel.
Every city sells a souvenir; in city i it costs prices[i - 1].
You leave your home city, travel by road to any city (staying home is allowed), buy exactly one souvenir there and go back home. On the way back you are carrying your purchase, so every road costs k times its usual price.
Return an array of length n whose i-th element (0-based) is the minimum total cost of such a trip for someone who lives in city i + 1. The road network may be disconnected.n=3, roads=[[1, 2, 3], [2, 3, 10]], prices=[20, 9, 4], k=2 → [18, 9, 4]
From city 1: go to city 2 (3), buy for 9 and come back (3 · 2 = 6), 18 in total, cheaper than 20 at home. City 2 buys locally for 9. City 3 buys locally for 4.
n=2, roads=[[1, 2, 1]], prices=[50, 10], k=1 → [12, 10]
From city 1 it pays to visit city 2: 1 + 10 + 1 = 12.
n=4, roads=[[1, 2, 5], [3, 4, 1]], prices=[7, 30, 30, 2], k=3 → [7, 27, 6, 2]
n=3, roads=[[1, 2, 3], [2, 3, 10]], prices=[20, 9, 4], k=2
[18, 9, 4]
Run checks the first 3 tests in your browser. Submit checks all 72 tests on the server, hidden ones included.