After having a bit too much to drink in the evening, you find yourself going on a long walk on a directed graph---but not too long, as there are no cycles. You start at vertex \textbf{0}, and whenever you are at a vertex, you will randomly leave the vertex along one of its outgoing edges with probability proportional to the weight of the edge. You continue walking until you reach a vertex that has no edges leaving it, after which you fall asleep. The length of your walk is the number of edges you traverse. Moreover, before leaving vertex \textbf{0}, you may choose one edge from anywhere in the graph that you do not like and ignore it during your walk (or you may choose to not ignore any of them). Determine the longest possible expected length of your walk. \InputFile The input consists of multiple test cases. Each test case begins with a line containing two integers \textbf{N}, \textbf{2} ≤ \textbf{N} ≤ \textbf{10000}, and \textbf{M}, \textbf{1} ≤ \textbf{M} ≤ \textbf{100000}, the number of vertices and edges in the graph, respectively. The next \textbf{M} lines each contain three integers \textbf{u}, \textbf{v}, and \textbf{w} (\textbf{1} ≤ \textbf{w} ≤ \textbf{1000}), indicating that there is a directed edge from vertex \textbf{u} to vertex \textbf{v} (numbered from \textbf{0} to \textbf{N−1}) with weight \textbf{w}. The input terminates with a line with \textbf{N = M = 0}. \OutputFile For each test case, print out a single line that contains the longest possible expected length of your walk. Your answer will be considered correct if it is within \textbf{10^\{−6\}} absolute or relative precision.