题目描述

战争时期，前线有 $n$ 个哨所，哨所之间通过 $m$ 条双向通信线路连接，每条线路传递信息需要花费固定天数。

指挥部设在第 $1$ 个哨所。当指挥部下达命令后，信会通过通信线路同时向所有相连的哨所传递；每个收到信的哨所也会立即向其相连的其他哨所传递。

请计算：所有 $n$ 个哨所都收到命令所需的最短时间。若存在哨所无法收到命令，输出 -1。

输入格式

第一行：两个整数 $n, m$，分别表示哨所数量和通信线路数量。 接下来 $m$ 行：每行三个整数 $i, j, k$，表示第 $i$ 个和第 $j$ 个哨所之间有一条双向线路，传递信息需要 $k$ 天。

输出格式

仅一行一个整数，表示完成送信的最短时间；若有哨所无法收到命令，输出 -1。

输入输出样例

输入 #1

样例

输入

4 4 

输出

1 2 4 
2 3 7 
2 4 1 
3 4 6

输出 #1

11

说明/提示

数据范围

• $1 \le n \le 100$
• $1 \le i, j \le n$
• $1 \le k \le 10^4$