A 市的电器城开张啦，琳琅满目的电器给市民的生活带来了很多便捷。为了方便大家购物，电器城推出了免费送达的服务，你在电器城购买的电器只要超过指定的金额，电器城会在第 2 天将电器免费送到你的家里。

由于给每户人家要送的电器比较多，家电城的货车又比较小，每次司机只能给一户人家派送电器，然后回电器城再取下一家要派送的电器送货。

某天，司机收到了当天要派送的所有电器的收货地址。该天一共要派送到 N-1 个收货地址。地址编号为 2 \sim N，其中编号为 1 的位置是电器城的地址。

该市有 M 条单向道路，并统计出了通过每条道路的需要的小时数。

请编程计算出，司机从电器城出发，送完所有的电器并回到电器城，最少需要多少个小时？

输入文件第一行包含一个正整数 N 和 M；

接下来 M 行， 每行三个正整数 X、 Y、 T， 表示该条道路为从 X 到 Y 的单向道路， 通过这条道路 需要 T 个小时。

满足 1≤X,Y≤N，1≤T≤10000， 输入保证任意两点都能互相到达。

输出包含一个整数，为最少需要的小时数。

对于 30\% 的数据，满足 1≤N≤200。

对于 100\% 的数据，满足 1≤N≤1000，1≤M≤100000。

图论