DUites are crazy about CROSSROADS AT SRCC . There’s a long student line in front of SRCC FOR ITS ENTRY. Here are the student line considerations. There can be max 2 incoming student lines merging at a guard point. Only one outgoing student line from any guard point. There can be multiple guard points & the student lines move uni-directionally. There will be only one entry point where all the student lines will take an entry from. There are multiple entry points exist for the DUites to reach the main entry point. “DUites” who are entering into the college premises don’t have any idea of Optimal Path & time required to reach the main entry point. So there is a need to design a system that can suggest the DUites what is the “Optimal Path” and its “Expected Time for reaching the main entry point and enjoy the event of lovely SUNIDHI CHAUHAN” The expected time of reaching the main entry point from a student line depends on the number of students in that student line plus the number of students in the other student lines.

Time taken to cross the main entry point is 1 time unit

Assume that there is a policeman standing on each guard point whose job is to open the main gate to send students from in-student line(s) to out-student line. If there are multiple in-student lines in front of main gate , the policeman will send DUites from each student line one by one alternatively.

For example, if there are 2 in-student lines containing 3 DUites each, student from student line1 will be sent first followed by student from student line2 followed by next student from student line1 and so on. It’s an alternate pick between the incoming student lines For the given problem, the input will consist of:
● No of entry gates: entries/exits where you can get on or off a particular student line.(<=150)
● No of student lines: Total number of student lines(<=500)
● "start_point" "end_point" #students(on the student line b/w start & end point) . Note: this is also the max number of students that can stand in this student line
● The travel time for each student line is held proportional to #students in that student line
Given the current snapshot of number of students on each student line, Calculate the minimum time for a student to reach the main entry point who is just about to enter any student line. Also, output the path that he should take to reach the main entry point in minimum time in the worst case(at each guard point, the policeman starts choosing students from the in-student line other than the one we are calculating the minimum time for).

Note : If multiple optimal paths are possible, print each of the path in a separate line sorted w.r.t to the first node and enjoy the event.

Input The first line contains the number of entry gates 'n'(<150). The second line contains the number of student lines 'e'(<500). The next 'e' lines contains three values: the start point, the end point and the number of students on this student line(This is also the max. number of students that can stand in this student line)

Output Optimal Time Path(s)