题目描述

对于一个给定的无向图，求指定两点的最短距离。

提示：

使用链式前向星+朴素的Dijkstra算法，可以通过前7组数据，后三组超时；

使用链式前向星+堆优化的Dijkstra算法，可以通过全部数据样例。

输入格式

第一行为整数n、m，表示图中点的个数和边的个数；

第二行为整数s、t，表示起点和终点的数字；

此后的m行，每行描述一条边，由三个整数u，v和w组成，表示顶点u到v之间有一条权值为w的边。

输出格式

一个整数，代表从s到t的最短距离。若不能到达则输出No。

输入/输出样例

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

4

数据范围

1≤n≤10^5，1≤m≤10^5，

1≤s, t≤n，

1≤u, v≤n，

1≤w≤10^3，所有边权值之和不超过int类型的数据范围

说明/提示

时间1000ms，内存256MiB