Tourist Huseyn
Huseyn have decided to travel to another country ,but in Corona Virus season it will be difficult to have a cheap road . The bus driver has a list of the N cities in his country and calculated which paths between these cities would give more money. Each path connects two cities. The cost of the path is how many the bus driver would earn by choosing this path . Path have to be chosen so that any two paths have one city in common. Calculate the maximum cost that bus driver can have.
####Input:The first line shows the number of cities N (1 ≤ N ≤ 300000 ) and the number of paths M (1 ≤ M ≤ 500000) . Cities indexes are from 1 to N. The following M lines contain three numbers each – a[i], b[i](1 ≤ a[i], b[i] ≤ N ) and p[i] (1 ≤ p[i] ≤ 1000000000 for all i ) ,where ai and bi are the two cities joined by the i-th path, and pi is the cost of the path. No two paths connect the same pair of cities.
####Output:Print a single number: the maximum possible cost.
####Explanation for the first sample case:
Picking paths 1–2, 1–3, 1–4 would give a cost of 4 and this is the correct answer. You can selectpaths 1–2,1–4,2–4 as well, but cost would then be smaller – 3 .