"In the fresh morning, there always gleams a star in the rosy sky. She is the brightest start - the Phosphor. Her rays are suspended high, but sometimes tremble around the white walls, as if she would like to share some touching stories with us. Since there appear the human beings, she has been always there, telling us everything she has heard and seen for thousands of years in the rolling world." Now let's meet one of its stories:
"A short time ago" - to her opinion, even thousands of years in men's eyes takes up a blink in her life – "my beam focused on a prince named Remmarguts, (what a strange language) who is recognized as the wisest and most kind-hearted man in his country UDF - United Delta of Freedom."
She proceeds to say, "that was a terribly cold day, and flakes of snow were falling outside, while one of them rested on a large box. The snowflake grew larger and larger; actually turn out to be a maiden in white! 'I am Goddess Uohzgnah and I am going to tell you the potential tragedy brought from Ahriman (the spirit of evil). The only way to prevent Ahriman's evil world-rebuilding from happening is to solve her puzzle successfully. We have tried our best, but failed to solve it. Wise guy, I will give you the only chance to protect your citizens. Take it –' "
That were N (4
Ahriman had also tied some HEAVY magic strings between some of them. The strings were of three different colors – white (peace), light green (nature) and light blue (people) (which are the three basic elements in Ahriman's so-called "ideal world").
"Goddess Uohzgnah handed two special magic stick to Prince Remmarguts, and told him the usage 'the first stick can make you sure about what color each string is (these three colors are very much alike); the second stick can disconnect any two connected pieces as you like' "
His aim was to cut off as many strings as possible (making it lighter) and to make the minimal number among three types of strings maximal (i.e., if we put the numbers of three different strings X, Y, Z, our aim is to make min{X, Y, Z} as large as we can). Meanwhile for any K (2
"Goddess Uohzgnah disappeared in Remmarguts' sight, but I know she was hiding there watching the whole course that our hero successfully solved the puzzle in a single day!" said the Phosphor, "Uohzgnah was affected by such a clever prince, and told him that this was only a joke. (Faint to death) Remmarguts didn't mind at all, because both of them fell in love..."
Hearing such an interesting story, dare you solve the puzzle then?
輸入描述
The first line contains two integer numbers N and M (N – 1
Each of the following lines contains three integer numbers A, B and C (1
We ensure at beginning of the puzzle, for an
輸出描述
After removing the strings, you should print a single line containing a single integer number, which is the smallest one among the numbers of three different colors in the remainder strings.
輸入例子
10 13
1 2 0
2 3 1
2 4 2
4 5 0
4 6 2
6 7 1
4 7 0
7 8 1
7 9 0
7 10 1
8 9 2
9 10 0
3 8 2
輸出例子
3
http://poj.org/problem?id=2439
