Description

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

Input Format

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 Format

Output one line containing a single integer, the answer.

7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1

7

Hint

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