Travel Fatigue in P Country

In country P there are n cities and m directed roads. For the i-th road, it goes from city u_i to city v_i with length w_i. It is guaranteed that $u_i<v_i$ for all roads.

A travel itinerary is a sequence of cities $x_1,x_2,\dots,x_k$ such that there is a road from $x_i$ to $x_{i+1}$ for each valid $i$. Let the length of the road from $x_i$ to $x_{i+1}$ be $y_i$, and define for each $1\le i\le k-1$,

where $\lor$ denotes the bitwise OR. The fatigue of the itinerary is defined as

where for a sequence of non–negative integers, $\operatorname{mex}(a_1,a_2,\dots,a_n)$ is the smallest nonnegative integer that does not appear in the sequence. For example, $\operatorname{mex}(0,2,3)=1$, $\operatorname{mex}(1,4)=0$, and $\operatorname{mex}(0,1,2,3,4)=5$.

For two cities s and t, define the distance $d(s,t)$ as the maximum fatigue among all itineraries from s to t. If there is no itinerary from s to t, then $d(s,t)=-1$. It is also given that $d(s,s)=0$ for every city s.

Your task is to compute the sum

Input constraints: The input is guaranteed to describe a directed acyclic graph (since every road satisfies $u_i<v_i$). You may assume that n and m are small enough so that a solution with state–space dynamic programming is feasible.

inputFormat

The first line contains two integers n and m — the number of cities and roads, respectively.

Each of the next m lines contains three integers u, v and w indicating that there is a directed road from city u to city v with length w.

outputFormat

Output a single integer denoting the sum of distances $\sum_{i=1}^{n}\sum_{j=1}^{n} d(i,j)$.

sample

3 3
1 2 0
2 3 1
1 3 2

-2