【问题描述】

战争时期，前线有 n 个哨所，每个哨所可能会与其他若干个哨所之间有通信联系。 信使负责在哨所之间传递信息，每条通信线路都需要花费一定的时间（以天为单位）。

指挥部设在第 1 个哨所。 当指挥部下达命令后，会向所有与其直接相连的哨所派出信使。 每个哨所在接到命令后，也会以同样方式继续向其他哨所传递信息。 直到所有 n 个哨所都接到命令，送信过程才算完成。

已保证每个哨所内有足够多的信使。

请计算完成整个送信过程所需的最短时间。 如果不是所有哨所都能收到信，则输出 −1。

【输入格式】

输入文件 msner.in：

• 第 1 行：两个整数 n 和 m，分别表示哨所数和通信线路数（1 ≤ n ≤ 100）
• 第 2 行到第 m+1 行：每行三个整数 i、j、k，表示第 i 个哨所和第 j 个哨所之间存在通信线路，且需要 k 天

【输出格式】

输出文件 msner.out，仅一行，一个整数，表示完成整个送信过程的最短时间；若无法完成，输出 −1。

【输入样例】

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

【输出样例】

11