题目描述

给定一个 $n$ 个点，$m$ 条边的带权有向图，计算任意两点最短路长度

输入格式

第一行两个整数 $n,m$ 第二行起 $m$ 行，每行三个整数 $u,v,w$ 表示从 $u$ 到 $v$ 有一条权值为 $w$ 的有向边

注：如果有重边，取最后输入的一条边

输出格式

输出所有任意两点最短路长度的或值

5 15
2 5 181
1 5 98
4 2 49
3 2 262
4 3 26
2 4 192
5 1 221
2 2 254
4 4 233
1 5 44
5 4 67
4 2 214
1 1 47
1 1 118
5 4 3

1023

数据范围

$1\le n \leq300$