포뮬러

슬라본스키브로드에서 몬테카를로를 본떠 시내 도로에서 포뮬러 1 경주를 열려고 한다. 도로망은 $N$개의 교차로와 $M$개의 도로로 이루어진다. 교차로에는 1부터 $N$까지 번호가 붙어 있다. 모든 도로는 양방향이고 길이가 서로 같으며, 서로 다른 두 교차로를 잇는다. 각 도로는 중요 도로이거나 일반 도로다. 이 도시에는 재미있는 성질이 있는데, 중요 도로만 사용해도 어느 교차로에서 다른 어느 교차로로든 갈 수 있다.

경주 코스는 다음과 같이 정한다.

1. 코스는 어떤 교차로에서 출발해 같은 교차로에서 끝난다.
2. 코스는 어떤 도로도 두 번 지나지 않는다. 같은 교차로는 여러 번 지나도 된다.
3. 코스는 모든 중요 도로를 포함한다.

도로를 가장 많이 쓰는 코스의 도로 수를 구하라.

첫째 줄에 자연수 $N$ ($1 \le N \le 29$)과 $M$ ($N - 1 \le M \le N \times (N-1)/2$)이 주어진다.

다음 $M$개의 줄에 세 정수 $A$, $B$, $T$가 주어진다 ($1 \le A, B \le N$, $A \ne B$). $T$는 0 또는 1이다.

$T$가 0이면 교차로 $A$와 $B$를 일반 도로가 잇는다는 뜻이고, 1이면 중요 도로가 잇는다는 뜻이다.

같은 두 교차로를 직접 잇는 도로가 둘 이상 주어지는 경우는 없다.

첫째 줄에 코스에 들어갈 수 있는 도로 수의 최댓값 $S$를 출력한다. 경주 코스를 만들 수 없으면 -1을 출력한다. $N$이 1이면 도로가 없으므로 0을 출력한다.

첫 번째 예제에서 코스는 1 -> 2 -> 3 -> 1 처럼 만들 수 있다.