Minimum Total Distance for Maximum Vertex‐Disjoint Routes

Elaxia has recently developed a passion for karate and has set himself an exercise regimen consisting of various workouts. However, so far he has only been able to maintain his morning runs. Every day, he runs from his dormitory (node 1) to his school (node $N$) along a given map. The map is represented as a network containing $N$ nodes (intersections) and $M$ streets. Each street connects two intersections and has an associated length.

Elaxia’s plan is cyclic – it spans several consecutive days. Since he dislikes repeating any route, the routes chosen for different days in the cycle must be vertex-disjoint except for the starting point (dormitory, node 1) and the destination (school, node $N$), which are not considered intersections for the disjoint condition. In other words, aside from nodes 1 and $N$, no intermediate node can appear in more than one route.

Furthermore, although Elaxia wishes to maximize the number of days in his cycle (that is, maximize the number of vertex‐disjoint routes), his endurance is poor and he wants the total running distance over the cycle to be as short as possible. In the special case where there exists a direct street from node 1 to node $N$, note that such a street can only be used once.

Your task is to design a plan that meets Elaxia’s requirements. Formally, given a map with $N$ nodes and $M$ streets, where each street is described by three integers u, v, w (indicating that there is a street connecting nodes u and v with length w), compute two numbers:

• The maximum number of vertex‐disjoint routes from node 1 to node $N$.
• The minimum total distance sum of these routes among all such sets.

Note: When a street directly connects node 1 and node $N$, it can be used at most once.

Hint: A standard approach is to transform the problem into a minimum cost maximum flow problem by splitting each vertex (except nodes 1 and $N$) into two nodes and assigning an edge of capacity 1 between them. Then, by adding edges corresponding to each street (treating the direct edge from 1 to $N$ specially), you can compute the desired values.

inputFormat

The first line contains two integers $N$ and $M$ ($2 \le N \le 500$, $1 \le M \le 10^4$), representing the number of nodes and the number of streets respectively.

Each of the following $M$ lines contains three integers u v w ($1 \le u, v \le N$, $1 \le w \le 10^5$), which denote that there is a street between nodes u and v with length w. It is guaranteed that the graph is undirected. If a street connects node 1 and node N directly, it can only be used once.

outputFormat

Output two integers separated by a space. The first integer is the maximum number of vertex‐disjoint routes from node 1 to node $N$, and the second integer is the minimum total distance if these routes are chosen optimally.

sample

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

2 14