QTGIFT3  Christmas is coming
English  Vietnamese 
Christmas will come next month, so DB is planning to give TN a wonderful gift.
The city that DB and TN are living has n intersections. Each direct connections between 2 intersections has its length. In the Christmas night, TN will wait at the tth intersection, and DB will start from the sth intersection go through some connections, to the date place.
Of course DB doesn’t want to make TN wait for long time, so he will choose the shortest path. He also want to know how many different shortest paths from s to t (there is at least one path).
Because the number of intersections and connections are too large, DB can’t calculate these himself, so he need you help.
Input
 First line : 3 positive integers, n, s and t (2 ≤ n ≤ 10^{5}, 1 ≤ s, t ≤ n, s ≠ t)
 n lines : the ith line contains 3 positive integers l, r, w, means there are direct connections from i to l, i to l + 1, ... i to r, each has length w (1 ≤ l ≤ r ≤ n, w ≤ 10^{6})
Output
 Two positive integers, length of the shortest path, and number of the shortest paths (modulo 10^{15}), separated by a space
Example
Input: 4 1 4 2 3 3 3 4 5 2 4 5 1 2 6 Output: 8 2
Detais: the two shortest paths are (1, 2, 4) and (1, 3, 4)
hide comments
Kata:
20150105 05:30:25
Thanks :D. I glad you enjoyed it. 

LeppyR64:
20141223 18:02:54
Interesting problem. I can't get past the O(n^2) graph density. 

Francky:
20141223 16:11:24
Please upload the image on spoj system.


Kata:
20141223 16:11:24
Yes. You can see the image. Problem edited. Last edit: 20141223 14:09:58 

રચિત (Rachit):
20141223 16:11:24
Are the connections directed? 

Jasmeet Singh:
20141223 16:11:24
Tried with Dijkstra with MinHeap and Dijkstra's without MinHeap (Find minimum by iterating over distance array) .. Both give TLE .. any ideas ? 
Added by:  Kata 
Date:  20141125 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own Problem 