P1339 [USACO09OCT] Heat Wave G

Given an undirected graph with $n$ vertices and $m$ edges, find the length of the shortest path from $s$ to $t$.

The first line contains four positive integers $n, m, s, t$. The next $m$ lines each contain three positive integers $u, v, w$, indicating an edge connecting $u$ and $v$ with length $w$.

Output one line containing a single integer, the answer.

Constraints For $100\%$ of the testdata, $1 \le n \le 2500$, $1 \le m \le 6200$, $1 \le w \le 1000$. Sample Explanation $5 \to 6 \to 1 \to 4$ is the shortest path, with length $3+1+3 = 7$. Translated by ChatGPT 5