Minimum Spanning Tree with Optimal A-B Connection

Let G=(V, E) be an undirected graph and let A, B be its two vertices. We say that a spanning tree T of graph G connects A and B optimally if and only if the edge distance between A and B in T equals the edge distance between A and B in G.
The edge distance between A and B is equal to the least possible number of edges on any path from A to B.



Figure 1. a) A weighted undirected graph consisting of 10 vertices and 13 edges. The weigths are depicted by the red numbers. The edge distance between vertices 5 and 9 is 4. The blue edges form a spanning tree which connects vertices 5 and 9 optimally and whose cost is minimal among all such spanning trees. b) A graph with 9 vertices and 12 edges. The blue edges again represent a spanning tree which connects vertices 3 and 6 optimally and is of a minimum cost.

The task

Given a weighted undirected graph and two its vertices A, B, find a spanning tree which connects A and B optimally and whose cost is minimal possible.


Input

The first input line contains four integers N, M, A and B separated by space. N is the number of vertices, M is the number of edges, A and B are identifiers of two vertices (all the vertices are numbered from 1 to N). Next, there are M lines with triples of integers V1, V2, W separated by space, representing an undirected edge of weight W between vertices V1 and V2. The edges are listed in random order.
It holds N ≤ 210000, M ≤ 250000. Each weight is a positive integer not greater than 200.

Output

The output contains one line with two integers L and C separated by space where L is the edge distance between A and B, and C is the minimum cost of a spanning tree that connects vertices A and B optimally.

Example 1

Input
10 13 5 9
1 2 1
1 3 2
2 4 2
3 5 1
3 7 2
4 7 4
4 9 2
5 6 2
6 7 4
7 8 1
8 9 3
6 10 3
10 8 2
Output
4 16

Example 2

Input
9 12 3 6
3 1 4
1 2 4
2 6 4
3 4 3
4 5 3
5 6 3
3 7 1
7 4 1
4 8 1
8 5 1
5 9 1
9 6 1
Output
3 17

Example 3

Input
8 16 7 3
7 8 1
8 1 3
1 2 1
2 3 2
3 4 1
4 5 3
5 6 1
6 7 2
7 1 1
1 3 4
3 5 2
5 7 3
6 8 1
8 2 3
2 4 2
4 6 2
Output
2 10
The data and solution of Example 1 and Example 2 are depicted in Figure 1a) and 1b), respectively.

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set