Problem: Going Home

Want to try solving this problem? You can submit your code online if you log in or register.

Going Home

Input File: standard input
Output File: standard output
Time Limit: 1 second
Memory Limit: 256 MB

Vlad and Tony work in different parts of the city but they enjoy walking home together.

The city can be thought of as a weighted undirected graph, where the N intersections are vertices and the M two-way roads (each with their own lengths) are edges. Intersections are numbered 1 to N. Vlad's office is at intersection 1, Tony's office is at intersection 2, and their house is at intersection N.

Every day, Vlad and Tony both leave work at the same time, walking at the same speed. Each of them takes a shortest path to their house, so that they arrive at the house as early as possible. There may be more than one shortest path from Vlad's office to their house. (Two Vlad-shortest-paths are considered different if they do not visit the same sequence of intersections.) Likewise, there may be more than one shortest path from Tony's office to their house.

Whenever Vlad and Tony walk along the exact same road in the same direction, starting and finishing at the same times, we say they spend quality time together. Vlad and Tony would like to spend as much quality time together as possible.

Your task is to determine how much quality time Vlad and Tony can spend together as they walk home. In addition, you should also determine how many different combinations of Vlad-shortest-paths and Tony-shortest-paths achieve this maximum amount of quality time. This number should be given modulo 1,000,000,007.

Input

The first line of input will consist of N and M separated by a space. Each of the following M lines describes a single road and is given in the form "aibiti", representing a road connecting intersection ai to intersection bi which takes ti minutes to travel along.

Each pair of intersections will be connected by at most one road. No road will connect an intersection to itself. You are guaranteed that there is a path from both intersections 1 and 2 to intersection N, i.e. it is possible for both Vlad and Tony to go home.

Output

The first line of output should consist of a single integer: the maximum amount of quality time Vlad and Tony can spend together as they walk home, given in minutes.

The second line of output should consist of a single integer: the number of different combinations of Vlad-shortest-paths and Tony-shortest-paths that achieve this maximum amount of quality time, modulo 1,000,000,007.

Sample Input 1

7 10
1 4 5
2 3 2
3 4 3
3 5 4
2 4 5
4 5 1
4 6 2
5 6 1
5 7 2
6 7 1


Sample Output 1

3
6


Sample Input 2

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


Sample Output 2

0
1


Explanation

In the first example, Vlad and Tony can spend 3 minutes of quality time together by meeting at intersection 4. Combinations of Vlad-shortest-paths and Tony-shortest-paths that result in maximum quality time together are:

Notice that although Vlad could take the shortest path 2  -> 3  -> 5  -> 7 home, this would not allow him to spend as much time with Tony.

In the second example, Tony and Vlad may not meet up at intersection 3 and walk together, because this would require them not to take shortest paths home. Instead, they must both take their unique shortest path home, spending zero quality time together.

Sample Input 3

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


Sample Output 3

0
4


Sample Input 4

13 19
1 3 1
1 4 1
3 5 1
4 5 1
1 6 2
2 7 1
2 8 1
7 5 1
5 8 1
2 6 2
5 9 1
5 10 1
6 11 1
6 12 1
9 13 1
10 13 1
11 13 1
12 13 1
6 13 2


Sample Output 4

2
11


Explanation

In the third example, Tony starts closer to home than Vlad. Since they must both leave at the same time and take shortest paths, Tony cannot "wait up" for Vlad and instead they spend zero quality time together.

Combinations of Vlad-shortest-paths and Tony-shortest-paths that result in maximum quality time together are:

1  -> 2  -> 3  -> 5   2  -> 3  -> 5
1  -> 2  -> 3  -> 5   2  -> 4  -> 5
1  -> 2  -> 4  -> 5   2  -> 3  -> 5
1  -> 2  -> 4  -> 5   2  -> 4  -> 5

In the fourth example, there are eleven paths allowing Vlad and Tony to achieve two minutes of quality time together.

For all subtasks, 1 ≤ N ≤ 100,000 and 1 ≤ M ≤ 100,000. All ti satisfy 1 ≤ ti ≤ 10,000.

• For Subtask 1 (20 points), there are no cycles and every intersection is reachable from every other intersection.

• For Subtask 2 (25 points), all ti = 1.

• For Subtask 3 (30 points), 1 ≤ N ≤ 1,000.

• For Subtask 4 (25 points), no further constraints apply.

Scoring

Your score for each test case will be 100% if both lines are correct, 50% if exactly one is correct, and 0% otherwise.

Privacy statement
Page generated: 28 January 2023, 12:35am AEDT