3928 - The Deep Dark Web

Created by Marcelo Fornet Fornés
Added by MarX (2017-07-07)
Limits
Total Time: 10000 MS | Test Time: 2000 MS |Memory: 512 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

The Deep Dark Web has grown in the last few years and, with this growth, many users are surfing in its deep and dark waters. DD4rk and 3ufR4t35 have been using this network for at least two years. They use this part of the web to design their master (and evil) plans. Part of their last plan involve sending massive amount of data from one server to another server.

The network consists of several servers located on unknown locations on the planet and connections between them. Each connection links exactly two servers and has a specific transfer rate measured in units of megabits per second (mbps). The information might go through a series of servers, but, due to the importance of the information, it is never split: it always travels on exactly one path from the source server to the destination server. The overall transfer speed of a path is equal to the speed of the slowest connection among the connections in the path. Obviously DD4rK uses the path with the fastest transfer rate.

As a consequence, this information transfer will last for days and 3ufR4t35 is getting anxious. She (or he) wants to increase the speed of the transfer. Since they need to finish this step of the plan as soon as possible, DD4rK decides to hack several connections and increase the speed of each connection. As she (or he) wants to avoid being detected, she will make the least amount of change possible to double the current speed. The total amount of change made on the network is the sum of all the megabits per second increased on each of the connections.

Your goal is to compute the current transfer speed (before DD4rK's hack) and the minimum total amount of change that DD4rK needs to make to double the current transfer speed.
;jsessionid=94381FB73AB68A969E17E290E9890ACF
La Internet Oscura y Profunda ("Deep Dark Web" en inglés) ha crecido en los últimos años y, con dicho crecimiento, muchos usuarios navegan en sus profundas y oscuras aguas. DD4rk and 3ufR4t35 han estado usando esta red por al menos dos años. Ellos la usan para diseñar sus macabros planes maestros. Parte de su  último plan involucra el envío masivo de una enorme cantidad de data desde un servidor a otro.

La red consiste en varios servidores localizados en sitios desconocidos ultrasecretos y conexiones entre esos servidores. Cada conexión interconecta a exactamente dos servidores y tiene una velocidad de transferencia específica medida en unidades de megabits por segundo (mbps). La información puede atravesar una serie de servidores, pero, debido a la criticidad de la información transmitida, nunca es dividida: esta siempre viaja sobre exactamente una ruta desde el servidor fuente hasta el servidor destino. La velocidad global de transferencia es igual a la velocidad de la conexión más lenta entre las conexiones en esa ruta. Obviamente, DD4rK usa una ruta que le ofrezca la velocidad global más alta posible.

Como consecuencia, el proceso de transferencia de la información puede durar días, lo cual desespera a 3ufR4t35. Ella (o él) desea aumentar la velocidad de transferencia. Como ellos necesitan terminar esta fase de su plan lo más antes posible, DD4rK decide "hackear" una o varias conexiones para incrementarles sus velocidades. Como ella (o él) no quiere ser detectado, harán la menor cantidad de cambio posible para duplicar la velocidad global actual. El cambio total en la red se mide como la suma de todos los incrementos en megabits por segundo de todas las conexiones alteradas.

Tu objetivo es calcular la velocidad global de transferencia actual (antes del "hack" de DD4rK) y el mínimo total de cambios que DD4rK necesita hacer para duplicar esa velocidad global de transferencia.
;jsessionid=94381FB73AB68A969E17E290E9890ACF
The Deep Dark Web has grown in the last few years and, with this growth, many users are surfing in its deep and dark waters. DD4rk and 3ufR4t35 have been using this network for at least two years. They use this part of the web to design their master (and evil) plans. Part of their last plan involve sending massive amount of data from one server to another server.

The network consists of several servers located on unknown locations on the planet and connections between them. Each connection links exactly two servers and has a specific transfer rate measured in units of megabits per second (mbps). The information might go through a series of servers, but, due to the importance of the information, it is never split: it always travels on exactly one path from the source server to the destination server. The overall transfer speed of a path is equal to the speed of the slowest connection among the connections in the path. Obviously DD4rK uses the path with the fastest transfer rate.

As a consequence, this information transfer will last for days and 3ufR4t35 is getting anxious. She (or he) wants to increase the speed of the transfer. Since they need to finish this step of the plan as soon as possible, DD4rK decides to hack several connections and increase the speed of each connection. As she (or he) wants to avoid being detected, she will make the least amount of change possible to double the current speed. The total amount of change made on the network is the sum of all the megabits per second increased on each of the connections.

Your goal is to compute the current transfer speed (before DD4rK's hack) and the minimum total amount of change that DD4rK needs to make to double the current transfer speed.
;jsessionid=94381FB73AB68A969E17E290E9890ACF

Input specification

The first line consists of two integers N and M (2 ≤ N ≤ 105, 1 ≤ M ≤ 105) denoting the number of servers on the network and the number of connections between them.

The second line contains two different integers S and T (1 ≤ S, TN) such that S represent the source server and T the target server.

The next M lines have the descriptions of all connections. Each line has three integers U, V, SP (1 ≤ U, VN; UV; 1 ≤ SP ≤ 104) that represents a connection between servers U and V with a speed of SP mbps. It is guaranteed that server S can reach server T through a series of these connections.
La primera línea consiste en dos números enteros N y M (2 ≤ N ≤ 105, 1 ≤ M ≤ 105), los cuales corresponden a la cantidad de servidores en la red y la cantidad de conexiones entre servidores.

La segunda línea contiene dos números enteros distintos S y T (1 ≤ S, TN), donde S representa el servidor fuente y T el servidor destino.

Las próximas M líneas contienen las descripciones de todas las conexiones. Cada línea tiene tres números enteros U, V y SP (1 ≤ U, VN; UV; 1 ≤ SP ≤ 104), los cuales representan la conexión entre servidores U y V con una velocidad de transferencia de SP mbps. Está garantizado que el T es alcanzable desde el servidor S a través de una serie de conexiones.
The first line consists of two integers N and M (2 ≤ N ≤ 105, 1 ≤ M ≤ 105) denoting the number of servers on the network and the number of connections between them.

The second line contains two different integers S and T (1 ≤ S, TN) such that S represent the source server and T the target server.

The next M lines have the descriptions of all connections. Each line has three integers U, V, SP (1 ≤ U, VN; UV; 1 ≤ SP ≤ 104) that represents a connection between servers U and V with a speed of SP mbps. It is guaranteed that server S can reach server T through a series of these connections.

Output specification

Print one line with two space-separated integers A and B, where A is the current speed of transfer and B is the minimal sum of the changes that DD4rK needs to do on the network to double the current speed of the transfer.

Imprime una línea con dos números enteros A y B separados por un espacio, donde A es la velocidad actual de transferencia y B es la mínima suma de todos los cambios que DD4rK necesita hacer en la red para duplicar la velocidad actual de transferencia.

The first line consists of two integers N and M (2 ≤ N ≤ 105, 1 ≤ M ≤ 105) denoting the number of servers on the network and the number of connections between them.

The second line contains two different integers S and T (1 ≤ S, TN) such that S represent the source server and T the target server.

The next M lines have the descriptions of all connections. Each line has three integers U, V, SP (1 ≤ U, VN; UV; 1 ≤ SP ≤ 104) that represents a connection between servers U and V with a speed of SP mbps. It is guaranteed that server S can reach server T through a series of these connections.

Sample input

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

Sample output

2 6

Hint(s)