Subaru and Rem are hunting down the white whale. They currently have a list of 
~N~ locations where the white whale has been rumoured to appear. There are 
~N-1~ roads that connect every location to every other location. The 
~i~th of these typically sees 
~t_i~ travelers per day.
If the white whale travels along these roads, it continually travels along a single path that sees a total of 
~K~ travelers per day, picked uniformly at random from all such paths. Doing so means that it will pass all locations that are on this path. Thus Rem asks Subaru ~N~ questions: if we wait at node 
~1, 2, \dots, N~, what is the probability we will encounter the whale?
Constraints
For all subtasks:
~0 \le t_i \le 1\,000\,000~
Subtask 1 [9%]
~1 \le N \le 100~
~1 \le K \le 100~
The network of roads forms the simplest possible line: For 
~1 \le i < N~, road ~i~ connects locations ~i~ and 
~i+1~.
Subtask 2 [12%]
~1 \le N \le 1\,000~
~1 \le K \le 1\,000\,000~
Subtask 3 [22%]
~1 \le N \le 200\,000~
~1 \le K \le 100~
Subtask 4 [57%]
~1 \le N \le 200\,000~
~1 \le K \le 1\,000\,000~
Input Specification
The first line of input will contain two space-separated integers, ~N~ and ~K~.
The next ~N-1~ lines will each contain 3 integers: 
~a_i, b_i, t_i~, indicating there is a road between locations 
~a_i~ and 
~b_i~, with ~t_i~ travelers per day.
Output Specification
You should output ~N~ lines, where each is the probability Rem and Subaru encounter the white whale, expressed as a fraction in lowest terms.
Sample Input
5 4
1 3 3
2 3 3
3 4 1
4 5 3
Sample Output
1 / 3
1 / 3
1 / 1
1 / 1
1 / 3
Explanation for Sample Output
The possible paths are:
~2\to 3\to 4~
~1\to 3\to 4~
~5\to 4\to 3~
Locations 
~3~ and 
~4~ appear on all ~3~ paths, but locations 
~1~, 
~2~, and 
~5~ only appear on a single path each.
Comments
what if a path has no chance? should it be
0 / 1?