某国在一场规模空前的大灾害过后，连接所有城市的公路都遭到了损坏而无法通车。政府派人修复这些公路。 给出该国的城市数 和公路数 ，公路是双向的。并告诉你每条公路的连着哪两个城市以及什么时候能修完这条公路。询问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）。

输入描述:

输入的第一行包含两个正整数 ，分别表示某国的城市数和公路数。 接下来  行，每行三个正整数 ，表示存在一条连着  两个城市的，需要花费时间  来完成修复的公路。

输出描述:

如果全部公路修复完毕仍然存在两个城市无法通车，则输出 ，否则输出最早什么时候可以使得任意两个城市都能够通车。