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