M. [USACO09OCT] Heat Wave G

Type: RemoteJudge

1000ms

125MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有一个 $n$ 个点 $m$ 条边的无向图，请求出从 $s$ 到 $t$ 的最短路长度。

第一行四个正整数 $n,m,s,t$ 。接下来 $m$ 行，每行三个正整数 $u,v,w$ ，表示一条连接 $u,v$ ，长为 $w$ 的边。

输出一行一个整数，表示答案。

【数据范围】
对于 $100\%$ 的数据， $1\le n \le 2500$ ， $1\le m \le 6200$ ， $1\le w \le 1000$ 。

【样例说明】
$5 \to 6 \to 1 \to 4$ 为最短路，长度为 $3+1+3 = 7$ 。