0 Judge
Code: 0
Your commander heard from the informants that the Dominion is transporting weapons via supply trains running on a rail network, and you have to intercept them before being shipped to the destination.
The rail network is modeled as an undirected graph of $V$ vertices and $E$ edges, where the vertices represent the transfer stations, and the edges represent bi-directional rails between stations. The stations are numbered from $1$ to $V$, and all trains depart from vertex $1$ for vertex $V$.
After carefully investigation, your commander decided to put your troops along rails in such a way that, no matter the routes those trains are taking, at least one bi-directional rail between stations are controlled by your troops.
For each rail $e_i$, it is estimated that a troop of size $c_i$ is required to be deployed along the rail in order to fully control it. Your task is to find a way to deploy your troops such that the sum of the troop sizes is minimized. If there are more than one ways to fulfill the requirement, you should break ties by minimizing the number of troops being deployed.
The first line of the input contains an integer $T$, the number of test cases. Each test case is formatted as follows.
$V\;E$
$u_{1}\;v_{1}\;c_{1}$
$u_{2}\;v_{2}\;c_{2}$
$\vdots$
$u_{E}\;v_{E}\;c_{E}$
The first line of each test case consists of 2 integers $V$ ($2 \leq V \leq 100$) and $E$ ($1 \leq E \leq 1000$) representing that there are $V$ vertices and $E$ edges in the modeled rail network.
Each of the following $E$ lines contains three integers $u_i$, $v_i$ ($1 \leq u_i, v_i \leq V$ and $u_i \neq v_i$), and $c_i$ ($1 \leq c_i \leq 1000$), representing a rail connecting stations $u_i$ and $v_i$, and you have to deploy a troop of size $c_i$ in order to control this rail.
You may assume that each station is reachable from any other stations by traveling through rails in the modeled network, and there is at most one rail connecting the same two stations.
For each test case, output 2 space-separated integers $s$ and $t$, which denotes the sum of troop sizes and the number of troops, respectively, in a line.
3
6 9
1 2 8
1 3 7
2 3 1
2 4 9
2 5 9
3 5 2
4 5 5
4 6 7
5 6 4
6 9
1 2 5
1 3 2
2 3 3
2 4 1
2 5 2
3 5 4
4 5 2
4 6 6
5 6 6
2 1
1 2 1
11 2
7 2
1 1
no