This question was asked in Sprinklr hiring challenge.
You are given a road network with N cities and M bidirectional roads. Each road has some positive amount of tax associated to it, meaning if there is a road connecting cities A and B with tax C, you need to pay C rupees to the government every time you use this road.
But you have a wildcard which can be used at most K times and when you use this wildcard while using using this road, you do not need to pay tax associated with that road. You are planning to visit one city this weekend, due to the limited budget you want to estimate minimum possible cost from your home city to every other city, so that you can choose the destination according to your budget. Your home city is a city numbered 1.
INPUT FORMAT
The first line of the input contains N, M, and K following M lines containing 3 integers U, V and C, meaning there is a road between cities U and V with tax C associated.
OUTPUT FORMAT
Print N space separated integers in a single line, ith integer indicating the minimum cost of travelling from city 1 to j
CONSTRAINTS
1 <= N,M <= 5 * 10^5
0 <= K <= 15
SAMPLE INPUT
4 4 1
1 2 2
2 3 3
1 3 6
3 4 11
SAMPLE OUTPUT
0 0 0 5