Dijkstra最短路径算法超时求助：优化方案或替代算法？

给定含n个节点（2≤n≤2e5）和m条边（1≤m≤4e5）的无向图，每条边包含节点v、u和权重w，要求输出从节点1到节点n的最短路径的节点数及路径；若不存在路径则输出-1。

我已实现基于堆的Dijkstra算法，逻辑正确，但存在超时问题。已完成堆实现优化、改用sys模块处理输入输出等操作，效率提升2倍仍未满足1秒时间限制。查阅资料10天仍未找到可行优化方案，现求助：

• 是否有更适合该问题场景的算法？
• 现有Dijkstra实现仍有哪些可优化的空间？

测试用例示例 #

输入1 #

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

输出1 #

3
1 4 5

输入2 #

8 9
1 2 4
2 3 6
3 1 5
1 4 5
1 5 5
5 4 7
5 6 1
6 7 1
7 8 1

输出2 #

5
1 5 6 7 8

输入3 #

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

输出3 #

-1

内容的提问来源于stack exchange，提问作者KarlLa