VS-Movies Group

Time limit: 1.4s Memory limit: 128MB Input: Output:

You just joined a group of fans of the vs-movies, the movies whose plot is the battle of two superheros. Each of the NN members of this group has to propose his favourite movie of this genre; the ii-th member chooses AiA_i vs BiB_i, a TiT_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 SS 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 SS 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 NN and SS, the number of members of the group and the total number of superheros. The following NN lines contain 33 integers each: AiA_i, BiB_i, TiT_i, the description of the favourite movie of the ii-th member.

Output data

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

Constraints and clarifications

  • 1N500 0001 \leq N \leq 500 \ 000.
  • 2S100 0002 \leq S \leq 100 \ 000.
  • 0Ai,BiS10 \leq A_i, B_i \leq S - 1 for each i=0N1i = 0 \leq N - 1.
  • AiBiA_i \neq B_i for each i=0N1i = 0 \leq N - 1.
  • 1Ti1091 \leq T_i \leq 10^9 for each i=0N1i = 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.
# Score Constraints
1 0 Examples
2 5 S=2S = 2
3 12 S=3S = 3
4 14 N15N \leq 15
5 22 N1 000N \leq 1 \ 000
6 26 N50 000N \leq 50 \ 000 and S50 000S \leq 50 \ 000
7 21 No additional limitations.

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 1212;
  • the second member’s list contains the second and third movies, with total duration of 77;
  • the third member’s list contains the third and fourth movies, with total duration of 66;
  • 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 66.

Log in or sign up to be able to send submissions!