택배기사 루루

루루는 신비한 하늘섬의 일일 택배기사이다. 루루의 일은 반품 택배 상자들을 회수하는 것이다.

하늘섬 사람들은 다음 규칙에 따라 반품 택배 상자를 놓는다.

• 섬과 섬을 잇는 각 다리 위에는 반품 택배 상자 하나가 놓여 있다.
• 하나의 다리에는 반드시 하나의 상자만 놓여 있다.
• 모든 상자의 크기는 서로 다르다.

루루도 자신만의 규칙을 정했다.

• 다리를 건널 때에는 반드시 그 다리 위의 택배 상자를 회수해야 한다.
• 한 번 지난 다리는 다시 지나지 않는다.
• 상자들은 회수한 순서대로 쌓는다. 먼저 회수한 상자가 아래에 놓이고, 나중에 회수한 상자가 그 위에 놓인다.
• 작은 상자 위에는 큰 상자를 쌓지 않는다.
• 상자의 순서를 바꿀 수 없다.
• 시작하는 섬은 자유롭게 정할 수 있다.

즉, 루루가 지나는 다리 위 상자의 크기는 지나간 순서대로 엄격히 감소해야 한다.

루루는 한 번의 시도로 자신이 옮길 수 있는 택배 상자의 최대 개수를 알고 싶어 한다. 루루가 규칙을 지키며 회수할 수 있는 택배 상자의 최대 개수를 구하는 프로그램을 작성하라.

입력은 다음과 같은 형식으로 주어진다.

$N\ M$ $u_1\ v_1\ c_1$ $u_2\ v_2\ c_2$ $\cdots$ $u_M\ v_M\ c_M$

$N$은 섬의 수, $M$은 다리의 수이다. $i$번째 다리는 $u_i$번 섬과 $v_i$번 섬을 잇고, 그 다리 위 상자의 크기는 $c_i$이다.

입력에서 주어지는 각 줄은 하나의 다리를 의미한다. 같은 두 섬을 잇는 다리가 여러 개 있을 수 있다.

루루가 규칙을 지키며 회수할 수 있는 택배 상자의 최대 개수를 출력한다.

• $1 \le N \le 200\,000$.
• $1 \le M \le 300\,000$.
• $1 \le u_i, v_i \le N$ ($1 \le i \le M$).
• $1 \le c_i \le 10\,000\,000$ ($1 \le i \le M$).
• $c_1, c_2, \ldots, c_M$은 모두 서로 다르다.