Hi Codeforces!!

I have tried this problem using Dijkstra, but it is giving me TLE :(, do you know a faster way to do it?

Thanks in advance!!! :)

-Problem Description-

You are given an undirected graph with weighted edges. You have to find the minimum length of path between vertex 0 and vertex n − 1 and the number of those paths with minimum length.

-Input-

There are many several test cases. Each test case begins with two positive integers n and m (2 ≤ n ≤ 100000, n − 1 ≤ m ≤ 100000) — the number of vertices and the number of edges in the graph. Each of the following m lines describes a corresponding edge. Each one contains three integers u, v and c (0 ≤ u, v < n, 1 ≤ c ≤ 1000) — these numbers denote an edge that connects vertices u and v and has weight c. The graph may contain multiple edges between the same pair of vertices and loops. It is guaranteed that the graph is connected.

-Output-

For each test case print one line with two numbers separated by a space, the minimum length of path between vertices 0 and n−1, and the number of paths between vertices 0 and n−1 with minimum length modulo 10^9 + 7.

-Sample Input-

5 12 4 3 3 3 2 1 0 2 2 2 0 2 0 1 4 4 1 2 4 1 5 0 1 2 3 1 1 3 3 1 2 1 1 0 3 1

-Sample Output-

4 3

Here is my code: https://ide.geeksforgeeks.org/gEDklVLLAF