水没都市

题号：NC236763
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

心灵早已被冲走
沉入谎言之中
在这深邃的深邃的水底
漂浮着陷入长眠
做着无法实现的梦
歌唱着想要消失

在这不会被爱的城镇中

世界由 $n$ 个城镇和 $m$ 条连接两个城镇的双向路径组成。开始时每条路有一个高度 $h_i$ 。

海水将会从 $1$ 号城镇进入，时刻 $t$ 时海水高度为 $t$ ，它会漫过所有从 $1$ 号城镇出发高度不超过 $t$ 的边。

具体地， $1$ 号点在时刻 $0$ 时就被淹没，若 $1$ 到 $x$ 存在某条路径上高度最高的边 $h_i$ 不超过 $t$ ，那么时刻 $t$ 时城镇 $x$ 将会被淹没。

海水不会淹没所有城镇。具体地，从时刻 $0$ 开始，若时刻 $t$ 时有城镇没有被淹没并且时刻 $t+1$ 时所有城镇都将被淹没，那么在时刻 $t$ 之后海水将不会上涨。

现在你可以使用魔法将某条边提高一格高度（即让 $h_i=h_i+1$ ），求最少使用多少次能够使得 $n$ 号城镇不会被淹没。

第一行输入两个正整数 $n,m$ $(2\leq n\leq 3000,1\leq m\leq 2\times 10^4)$ 分别表示城镇数量和路径数量。

接下来 $m$ 行每行三个正整数 $x,y,h$ $(1\leq x,y\leq n,x\neq y,1\leq h\leq 10^9)$ 表示有一条连接 $x$ 号和 $y$ 号城镇的双向路径，高度为 $h$ 。

保证图联通。

输出一行一个正整数表示需要的最少魔法次数。

示例1

复制

复制