You are given road network with N cities and M bi-directional 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 will need to pay C rupees to the government every time when you use this road,↵
but you have a wildcard which can be used at most K times and when you are using this wildcard while using the road, you do not need to pay tax associated to road.↵
You are planning to visit one city this weekend, due to 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 the budget.↵
Your home-city is a city numbered with 1.↵
↵
**Input Format:**↵
First line of input contains N,M and K following M lines contains 3 integer U V C , meaning there is a road↵
between cities U and V with tax associated.↵
↵
**Output Format:**↵
Print N space separated integers in a single line, ith integer indicating the minimum cost of travelling from city 1 to i.↵
↵
**Sample Input**↵
4 4 1↵
1 2 2↵
2 3 3↵
1 3 6↵
3 4 11↵
↵
↵
**Sample Output**↵
0 0 0 5
but you have a wildcard which can be used at most K times and when you are using this wildcard while using the road, you do not need to pay tax associated to road.↵
You are planning to visit one city this weekend, due to 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 the budget.↵
Your home-city is a city numbered with 1.↵
↵
**Input Format:**↵
First line of input contains N,M and K following M lines contains 3 integer U V C , meaning there is a road↵
between cities U and V with tax associated.↵
↵
**Output Format:**↵
Print N space separated integers in a single line, ith integer indicating the minimum cost of travelling from city 1 to i.↵
↵
**Sample Input**↵
4 4 1↵
1 2 2↵
2 3 3↵
1 3 6↵
3 4 11↵
↵
↵
**Sample Output**↵
0 0 0 5
