You are a girl. You are a young girl. You are a young and beautiful girl. Based on many reasons above, someone always wants to meet you. And you always want to avoid someone. Some day, your friends finally collect enough information about someone to analysis. These data are the probability that someone appears in every road. Now, you want to take the course. But you don’t want to meet someone. You can compute the probability before going out.
At first, the map records every possible path from the dormitory to the classroom. Guarantees the map doesn’t have any cycle. In every location, you have equal probability to go to the next locations. In every road, you have the probability that someone appears. Please output the probability that you will meet someone.
Each test case starts with a line containing two integers n(2<=n<=100) and m indicating the number of locations on the map and the number of the roads. Following this are m lines, each containing 3 integers representing the endpoints of the directed road ui, vi (0<=ui,vi<=n) and the probability that someone appears in this road pi (0<=pi<=100). The summation of pi will be 100. The map of the path doesn’t have any cycle. The number of the dormitory and the classroom are 0 and n-1.
Output the probability that you meet someone.