2065 - Invasion

Created by Ray Williams Robinson Valiente
Added by ymondelo20 (2012-10-12)
Limits
Total Time: 30000 MS | Test Time: 2000 MS |Memory: 62 MB | Output: 64 MB | Size: 29 KB
Enabled languages
Available in

Description

Our planet has been invaded by powerful alien forces. Being the leader of the resistance, you are trying to come up with a plan to cut the enemy’s supply lines. You have a map describing the field where the enemy’s supply source and headquarters are located, as well as some other important points such as battle bunkers and control access point, creating all of them a great network where all points are connected by secured tunnels. Knowing there is more than one way to get to the headquarters from the supply source, the enemy will distribute the delivery groups as much as possible, and so, you can’t leave any path available. But, there are a couple of things to take care about: first, your forces are not very large, so you need a way to cut all paths but destroying as few tunnels as possible, in order to be sure that you have enough men to assign to the mission; second, blowing up each tunnel requires a specific explosive charge, and as you don’t know how much longer the invasion will take, you have to save as much explosive as possible. In other words, the minimum necessary resources must be used. So, you will destroy the tunnels that require the least amount of explosives and, if there is more than one way to do this, you will choose the one with the least number of tunnels.
Our planet has been invaded by powerful alien forces. Being the leader of the resistance, you are trying to come up with a plan to cut the enemy’s supply lines. You have a map describing the field where the enemy’s supply source and headquarters are located, as well as some other important points such as battle bunkers and control access point, creating all of them a great network where all points are connected by secured tunnels. Knowing there is more than one way to get to the headquarters from the supply source, the enemy will distribute the delivery groups as much as possible, and so, you can’t leave any path available. But, there are a couple of things to take care about: first, your forces are not very large, so you need a way to cut all paths but destroying as few tunnels as possible, in order to be sure that you have enough men to assign to the mission; second, blowing up each tunnel requires a specific explosive charge, and as you don’t know how much longer the invasion will take, you have to save as much explosive as possible. In other words, the minimum necessary resources must be used. So, you will destroy the tunnels that require the least amount of explosives and, if there is more than one way to do this, you will choose the one with the least number of tunnels.
Our planet has been invaded by powerful alien forces. Being the leader of the resistance, you are trying to come up with a plan to cut the enemy’s supply lines. You have a map describing the field where the enemy’s supply source and headquarters are located, as well as some other important points such as battle bunkers and control access point, creating all of them a great network where all points are connected by secured tunnels. Knowing there is more than one way to get to the headquarters from the supply source, the enemy will distribute the delivery groups as much as possible, and so, you can’t leave any path available. But, there are a couple of things to take care about: first, your forces are not very large, so you need a way to cut all paths but destroying as few tunnels as possible, in order to be sure that you have enough men to assign to the mission; second, blowing up each tunnel requires a specific explosive charge, and as you don’t know how much longer the invasion will take, you have to save as much explosive as possible. In other words, the minimum necessary resources must be used. So, you will destroy the tunnels that require the least amount of explosives and, if there is more than one way to do this, you will choose the one with the least number of tunnels.

Input specification

Input begins with a line with two integers, N (4 <= N <= 5000) denoting how many points there are in the map and M (1 <= M <= 30000) saying the number of secured tunnels. M lines then, each one describing a tunnel with 3 integers, a, b (1 <= a, b <= N) and c (1 <= c <= 1000) meaning there is a tunnel between points a and b in the map, and you need c units of explosive charges to blow it up. Point number 1 is the supply source and point N is the enemy headquarters. No two tunnels connect the same pair of points. No tunnel connects a point in the field with itself.
Input begins with a line with two integers, N (4 <= N <= 5000) denoting how many points there are in the map and M (1 <= M <= 30000) saying the number of secured tunnels. M lines then, each one describing a tunnel with 3 integers, a, b (1 <= a, b <= N) and c (1 <= c <= 1000) meaning there is a tunnel between points a and b in the map, and you need c units of explosive charges to blow it up. Point number 1 is the supply source and point N is the enemy headquarters. No two tunnels connect the same pair of points. No tunnel connects a point in the field with itself.
Input begins with a line with two integers, N (4 <= N <= 5000) denoting how many points there are in the map and M (1 <= M <= 30000) saying the number of secured tunnels. M lines then, each one describing a tunnel with 3 integers, a, b (1 <= a, b <= N) and c (1 <= c <= 1000) meaning there is a tunnel between points a and b in the map, and you need c units of explosive charges to blow it up. Point number 1 is the supply source and point N is the enemy headquarters. No two tunnels connect the same pair of points. No tunnel connects a point in the field with itself.

Output specification

Output a single line with the minimum number of explosive charges required to cut all possible paths between supply source and headquarters, as well as the minimum number of tunnels required to be destroyed. Both integers should be separated by a single space.
Output a single line with the minimum number of explosive charges required to cut all possible paths between supply source and headquarters, as well as the minimum number of tunnels required to be destroyed. Both integers should be separated by a single space.
Input begins with a line with two integers, N (4 <= N <= 5000) denoting how many points there are in the map and M (1 <= M <= 30000) saying the number of secured tunnels. M lines then, each one describing a tunnel with 3 integers, a, b (1 <= a, b <= N) and c (1 <= c <= 1000) meaning there is a tunnel between points a and b in the map, and you need c units of explosive charges to blow it up. Point number 1 is the supply source and point N is the enemy headquarters. No two tunnels connect the same pair of points. No tunnel connects a point in the field with itself.

Sample input

4 4
1 2 3
2 3 4
3 1 2
3 4 3

Sample output

3 1

Hint(s)

In the example above, destroying tunnel between 3 and 4 will invalidate all possible paths. No other tunnel destruction shall cause that effect.
In the example above, destroying tunnel between 3 and 4 will invalidate all possible paths. No other tunnel destruction shall cause that effect.
In the example above, destroying tunnel between 3 and 4 will invalidate all possible paths. No other tunnel destruction shall cause that effect.