Courier Lulu

Lulu is a one-day courier on the mysterious sky islands. Lulu's job is to collect returned delivery boxes.

The people of the sky islands place returned boxes according to the following rules.

• Each bridge connecting two islands has exactly one returned delivery box on it.
• Each bridge has exactly one box.
• All box sizes are distinct.

Lulu also made the following rules.

• Whenever Lulu crosses a bridge, Lulu must collect the box on that bridge.
• Lulu never crosses the same bridge more than once.
• Boxes are stacked in the order they are collected. A box collected earlier is placed below a box collected later.
• Lulu must not place a larger box on top of a smaller box.
• Lulu cannot reorder the boxes.
• Lulu may choose any starting island.

Equivalently, the sizes of the boxes on the bridges Lulu crosses must be strictly decreasing in the order of traversal.

Find the maximum number of boxes Lulu can collect in one attempt while following all rules.

The input is given in the following format.

$N\ M$ $u_1\ v_1\ c_1$

Print the maximum number of boxes Lulu can collect while following all rules.

• $1 \le N \le 200\,000$.
• $1 \le M \le 300\,000$.
• $1\le {}_{}$ ().