Bear and Clique Distances

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Bearland consists of N cities, numbered 1 through N. Cities are connected with bidirectional roads.
Cities 1 through K were built a long time ago, when citizens liked order and regularity. Each pair of those old cities is connected with a road of length X. Note that this description generates K*(K1)/2 roads.
There are M newer roads, not necessarily of the same lengths. The ith of them connects cities a_{i} and b_{i} and has length c_{i}.
There is no road that connects a city to itself. All M+K*(K1)/2 roads are distinct (ie. no two of them connects the same pair of cities). It's guaranteed that it's possible to get from every city to every other city, using one or more roads.
Limak, a bear, lives in the city S. In order to plan a trip to some other city, for every city he wants to know how quickly he can get there. Can you help him and find the distance from S to every city?
The distance between two cities is the minimum total length of a path (sequence of roads) between the two cities.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains five integers N, K, X, M and S, denoting the number of cities, the number of old cities, the length of a road between every two old cities, the number of newer roads, and the city where Limak lives, respectively.
Each of the following M lines contains three integers a_{i}, b_{i} and c_{i}, denoting a road of length c_{i} between cities a_{i} and b_{i}.
As guaranteed above: no two cities are connected with more than one road, no road connects a city to itself, and it's possible to get from every city to every other city.
Output
For each test case, output a single line containing N integers. The ith of them should denote the distance from the city S to the city i. The distance from S to S is simply 0.
Constraints
 1 ≤ T ≤ 3
 2 ≤ K ≤ N ≤ 10^{5}
 0 ≤ M ≤ 10^{5}
 1 ≤ S, a_{i}, b_{i} ≤ N
 1 ≤ X, c_{i} ≤ 10^{9}
Subtasks
 Subtask #1 (45 points): 2 ≤ K ≤ 500
 Subtask #2 (55 points): Original constraints.
Example
Input: 3 5 4 100 2 3 1 5 50 5 3 160 5 4 100 2 3 1 5 50 5 3 140 8 3 15 7 5 3 4 10 4 5 20 5 6 10 6 1 7 3 7 1000 7 8 50 3 5 1000000000 Output: 100 100 0 100 150 100 100 0 100 140 17 32 30 20 0 10 1030 1080
Explanation
Test case 1. There are N = 5 cities. The first K = 4 of them are all connected with each other with roads of length X = 100. There are M = 2 extra roads:
 Cities 1 and 5 are connected with a road of length 50.
 Cities 5 and 3 are connected with a road of length 160.
We are asked to compute distances to all cities from the city S = 3. Note that the distance from a city to itself is 0, and this is why the third number in the ouput is 0.
Author:  errichto 
Editorial  https://discuss.codechef.com/problems/CLIQUED 
Tags  april17, easy, errichto, graphtheory 
Date Added:  3042017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 