Alice studies in one university in Dalian. You may not know that she is an idiot in finding the right way to somewhere. One day, she got lost on her way to a teaching building. Believe it or not, she got lost on the campus where she had lived for three years. By the way, she is a little lazy, so she always chooses the shortest possible way to go.
Last night, Alice had a dream that she was in Wonderland. She was shown a map of this place. As far as she can remember, there are $N$ towns numbered from 1 to $N$, connected by $M$ bi-directed roads. Now, she was in the #$1$ town, heading for the #$N$ town. Alice had an ability in her dream that she could build another (only one) road not existing on the map before, the length was arbitrarily selected by Alice. Note that multiple edges and self-loops are not allowed after the edge added.
Now, she gets an idea that she adds one road so that the number of the shortest paths from the #$1$ town to the #$N$ town increased would be no less than $X$ ($X$ is given). To get the job done, Alice needs to choose two distinct towns which are not yet connected directly by an existing road and then links them up with a new road. As to the weight, it is a positive integer determined at her will. By the way, Alice is quite clever much of the time, but sometimes gets confused just for no reason and unfortunately, in her dream, she was confused by this problem. Alice wanted to know how many different choices she had when choosing those two towns. Note that choosing town A and B is considered the same as choosing town B and A. Can you help her?