ml3 | VS-Movies Group

You just joined a group of fans of the vs-movies, the movies whose plot is the battle of two superheros. Each of the $N$ members of this group has to propose his favourite movie of this genre; the $i$-th member chooses $A_i$ vs $B_i$, a $T_i$ minutes long movie.

This night the members will watch some of the movies, following the strict rules of the group:

• The first member will present his movie, telling the story of the two superheros in it.
• Then all the members will watch that movie.
• After the movie ends another member proposes his chosen movie, with the only rule that the story of exactly one of the two superheros in it has already been told.
• After explaining the story of the other hero, all the members will watch that movie.
• This process is repeated until all the $S$ superheros are present in at least a movie.

Selecting the order in which the movies are watched is not an easy task, especially since every member wishes to show his favourite movie to the other members. To avoid any conflicts all the members share their favourite movie with each other and each member writes his proposal list: the list of movies to watch, which of course will include his favourite movie.

To maximise the probability of being selected, each list should be as short as possible; that is, the sum of the duration of the selected movies should be minimized. Of course, all the $S$ superheros must still be present in each proposal list.

You want to help to speed up this process by writing a program that, given the list of favourite movies, finds the duration of the optimal plan for each member.

Input data

The first line contains the integers $N$ and $S$, the number of members of the group and the total number of superheros. The following $N$ lines contain $3$ integers each: $A_i$, $B_i$, $T_i$, the description of the favourite movie of the $i$-th member.

Output data

You need to write $N$ lines with an integer each: the duration of the shortest plan that contains the $i$-th movie and involves all the superheros.

Constraints and clarifications

• $1 \leq N \leq 500 \ 000$.
• $2 \leq S \leq 100 \ 000$.
• $0 \leq A_i, B_i \leq S - 1$ for each $i = 0 \leq N - 1$.
• $A_i \neq B_i$ for each $i = 0 \leq N - 1$.
• $1 \leq T_i \leq 10^9$ for each $i = 0 \leq N - 1$.
• There could be more than one movie involving the same pair of heroes.
• It’s always possible to find a plan.

Example 1

stdin

4 3
0 1 10
0 1 5
0 2 2
1 2 4

stdout

12
7
6
6

Explanation

In the first sample case, each member presents the following lists:

• the first member’s list contains the first and third movies, with total duration of $12$;
• the second member’s list contains the second and third movies, with total duration of $7$;
• the third member’s list contains the third and fourth movies, with total duration of $6$;
• the fourth member’s list is the same list of the third member.

Example 2

stdin

3 4
0 1 1
0 2 2
0 3 3

stdout

6
6
6

Explanation

In the second sample case, all the three movies must be present in each one of the proposed lists. This means that each member presents the same list, whose total duration is $6$.