问题 D: 有向图的函数求值
内存限制：1024 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：11
解决：1
题目描述
现在给你一个有n个点m条边的有向图，我们定义一个函数f(s,t,k)，对于每一个f(s,t,k)的值为点s到点t并且只能经过点1或者点k的最短路径。先要求输出
输入
n (1<=n<=400)
m (0<=m<=n*(n-1))
a1 b1 c1
a2 b2 c2
....
ai bi ci
(表示有一条从ai到bi的边并且长度为ci)
(1<=ai,bi<=n)
(1<=ci<=1e6)
m (0<=m<=n*(n-1))
a1 b1 c1
a2 b2 c2
....
ai bi ci
(表示有一条从ai到bi的边并且长度为ci)
(1<=ai,bi<=n)
(1<=ci<=1e6)
输出
样例输入 复制
3 2
1 2 3
2 3 2
样例输出 复制
25