Matcom Online Grader

Debido a la irregularidad de las lluvias en esta época del año, el dueño de un parque está desarrollando un plan de evacuación para que los visitantes no se mojen. Sin embargo, las predicciones de clima no son siempre correctas. Con el propósito de minimizar las falsas alarmas, el dueño quiere que la alarma suene tan tarde como sea posible pero dándoles a los visitantes suficiente tiempo para que lleguen a algún refugio.

El parque tiene F (1 <= F <= 200) atracciones. Un conjunto de P (1 <= P <= 1500) caminos las conecta. Los caminos en el parque son anchos, de tal manera que cualquier número de visitantes puede recorrer un camino en cualquier dirección.

Algunas atracciones tienen refugios para lluvia bajo los cuales las personas pueden protegerse. Estos refugios son de tamaño limitado , por lo tanto un solo refugio puede no ser capaz de albergar a todos los visitantes. Las atracciones son pequeñas comparadas con los caminos y las personas no requieren ningún tiempo para atravesarlas mientras buscan refugio.

Calcule la cantidad mínima de tiempo antes de que la lluvia comience en el que la alarma debe sonar de tal forma que cada visitante pueda conseguir albergue en algún refugio.

Input

Línea 1: Dos enteros separados por espacio: F y P

Líneas 2...F + 1: Dos enteros separados por espacio que describen una atracción. El primer entero     (rango: 0...1000) es el número de visitantes en esa atracción. El segundo entero (rango: 0...1000) es el número de visitantes que el refugio en esa atracción puede albergar. La línea i+1 describe a la atracción i.

Líneas F + 2...F + P + 1: Tres enteros separados por espacio que describen  un camino. El primer y el segundo entero (ambos en el rango 1...F) dicen cuáles atracciones están conectadas por el camino. El tercer entero  (rango: 1...1.000.000.000) es cuánto se demora una persona en recorrerlo.

Output

Línea 1: La cantidad mínima de tiempo requerida para que todas las personas lleguen a un refugio, asumiendo que ellos planeen sus rutas de forma óptima. Si no es posible que todas los visitantes lleguen a un refugio, dé como salida “-1”.

Sample test(s)

Hints

En 110 unidades de tiempo, dos visitantes de la atracción 1 pueden albergarse en el refugio en esa atracción, cuatro visitantes de la atracción 1 pueden albergarse en el refugio del campo 2, y el visitante restante de la atracción 1 puede llegar a la atracción 3 y unirse a los visitantes en esa atracción para albergarse en el refugio de la atracción 3. A pesar de haber otros planes que pondrían a todas las vacas bajo un refugio, ninguno de ellos lo hará en menos de 110 unidades de tiempo.