teddy online judge

93. Necesitamos Otro Ride

Limite de tiempo : 3 seg.   Total runs : 129  Aceptados : 13

Los compañeros de tu clase de Introducción a la Teoría de la Computación (ITC) decidieron hacer una reunión en casa de Joe para relajarse de los exámenes. Desafortunadamente, después de toda esa programación, todos están demasiado cansados para caminar. Afortunadamente, entre todos tienen suficientes carros para llevar a todos.

Joe se acuerda que necesita detenerse en el supermercado en el camino para comprar hamburguesas y refresco. Jenn propone que se detengan en su casa para pasar por un frisbee. Jim decide que no le gustan las hamburguesas, y quiere pasar por pizza antes de llegar. Después de pasar tanto tiempo en el laboratorio, los ojos de Jerry se han vuelto muy sensibles a la luz del sol, así que necesita pasar a su casa por sus lentes de sol.

Y así se la llevaron: cada persona necesita detenerse para hacer algo en el camino. A este ritmo, los amigos se preocupan de que se hará de noche para el tiempo en el que lleguen a casa de Joe. Tuvieron una discusión acalorada acerca de quién debería ir en el coche de quién para minimizar el tiempo para que todos lleguen a casa de Joe. La discusión en sí misma, claro, desperdicia tiempo precioso que se podría invertir mejor en la reunión.

Para ayudar al grupo, necesitas escribir un programa para detener la discusión calculando la asignación óptima de personas a carros. El tiempo de trayecto en general es el máximo de los tiempos de trayecto de cada carro. Una asignación óptima es aquella que minimiza el tiempo de trayecto general.

Tu programa será alimentado con una representación de los caminos en la ciudad, en la forma de distancias entre puntos de interés. Asumiendo que cada carro siempre viaja a 60 kilómetros por hora (un kilómetro por minuto). Cada parada (en un supermercado, en casa de alguien, etc.) toma exactamente cinco minutos.

Aunque los amigos tienen muchos carros entre ellos, para ser buenos con el medio ambiente, deciden no llevar más carros de los necesarios. Cada carro puede llevar a lo más a cinco personas.

Entrada

La primer línea de la entrada contiene un entero N_c (1 ≤ N_c ≤ 100), que contiene el número de casos de prueba. La primer línea de cada caso de prueba contiene dos enteros n y m (1 ≤ n ≤ 15, 1 ≤ m ≤ 1000), el número de personas en el grupo y el número de caminos en la ciudad. Los lugares que deben ser visitados en el camino están numerados de 1 hasta n. El campus tiene el número 0 y la casa de Joe el número n + 1. Las siguientes m líneas cada una contiene tres enteros describiendo un camino. Los primeros dos enteros están en el rango 0 a n+1 inclusive, y describe los dos lugares que están conectados por el camino. El tercer entero especifica la longitud del camino en kilómetros. Ningún camino medirá menos de un kilómetro ni medirá más de 1000. Un camino puede ser tomado en ambos sentidos. Se garantiza que siempre existe una secuencia de caminos conectando cada lugar con cualquier otro lugar.

Salida

Para cada caso de prueba, imprime una línea con el número del caso, seguido un entero que represente el número de minutos requeridos para que todos lleguen a casa de Joe usando una asignación óptima de personas a carros. Sigue el formato de ejemplo.

Entrada/Salida de ejemplo

1
1 2
0 1 15
1 2 10

Caso 1: 30