## THICC '17 P6 - Tunnels

View as PDF

Points: 15 (partial)
Time limit: 0.3s
Java 8 1.0s
Python 1.4s
Memory limit: 256M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

On yet another of his adventures, Brian Bipai loses his way in an underground network of tunnels. Fortunately, he brought a map with him.

The map of the tunnel system identifies a series of points labelled from to . There are tunnels that each connect a distinct pair of points with a distance of . Each point can be reached from any other point by exactly one pathway of tunnels.

Brian Bipai does not know which of the points on the map he is located at. He knows that an exit must exist somewhere, but not where it is. However, he observes (based on his nearby surroundings) that he is definitely located at a point with connecting tunnels.

Brian Bipai would like you to determine all points on the map where he could potentially be at. Furthermore, for each of those points , determine the minimum distance that he has to travel in order to optimally search the entire underground network of tunnels for the exit.

#### Constraints

For of the points, .

#### Input Specification

The first line contains two integers and . The following lines each contain three spaced integers: , , and .

#### Output Specification

For each possible point that Brian Bipai could be at, print and separated by a space on its own line. All must be stated in increasing order.

#### Sample Input

6 3
1 3 1
2 3 1
3 4 3
4 5 2
4 6 2

#### Sample Output

3 13
4 14

#### Explanation

Brian Bipai could be located at point or point .
If he begins at point , then his optimal search path would be , taking a total distance of .
If he begins at point , then his optimal search path would be , taking a total distance of .