题目描述

这是一道最短路模板题。

给定$N个点，M条边$，给定起点$st$，终点$en$。

求起点到终点的最短路

输入格式

第一行，两个整数，表示$N,M$。

接下来$M$行，每行三个正整数$x,y,v$，表示$x到y有一条权值为v的有向边$

最后一行两个整数$st,en$.

输出格式

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

如果起点到不了终点输出 "No Solution!"(输出双引号内容)

样例数据

input

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

output

10

数据规模与约定

保证$2 \leq N \leq 10^4$，$1 \leq M \leq 10^5$。

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$