1184_E1. Daleks' Invasion (easy)
Heidi found out that the Daleks have created a network of bidirectional Time Corridors connecting different destinations (at different times!). She suspects that they are planning another invasion on the entire Space and Time. In order to counter the invasion, she plans to deploy a trap in the Time Vortex, along a carefully chosen Time Corridor. She knows that tinkering with the Time Vortex is dangerous, so she consulted the Doctor on how to proceed. She has learned the following:

  * Different Time Corridors require different amounts of energy to keep stable. 
  * Daleks are unlikely to use all corridors in their invasion. They will pick a set of Corridors that requires the smallest total energy to maintain, yet still makes (time) travel possible between any two destinations (for those in the know: they will use a minimum spanning tree). 
  * Setting the trap may modify the energy required to keep the Corridor stable. 



Heidi decided to carry out a field test and deploy one trap, placing it along the first Corridor. But she needs to know whether the Daleks are going to use this corridor after the deployment of the trap. 

She gives you a map of Time Corridors (an undirected graph) with energy requirements for each Corridor.

For a Corridor c, E_{max}(c) is the largest e ≤ 10^9 such that if we changed the required amount of energy of c to e, then the Daleks may still be using c in their invasion (that is, it belongs to some minimum spanning tree). Your task is to calculate E_{max}(c_1) for the Corridor c_1 that Heidi plans to arm with a trap, which is the first edge in the graph.

Input

The first line contains integers n and m (2 ≤ n ≤ 10^5, n - 1 ≤ m ≤ 10^6), number of destinations to be invaded and the number of Time Corridors.

Each of the next m lines describes a Corridor: destinations a, b and energy e (1 ≤ a, b ≤ n, a ≠ b, 0 ≤ e ≤ 10^9).

It's guaranteed, that no pair \\{a, b\} will repeat and that the graph is connected — that is, it is possible to travel between any two destinations using zero or more Time Corridors.

Output

Output a single integer: E_{max}(c_1) for the first Corridor c_1 from the input.

Example

Input

3 3
1 2 8
2 3 3
3 1 4


Output

4

Note

After the trap is set, the new energy requirement for the first Corridor may be either smaller, larger, or equal to the old energy requiremenet.

In the example, if the energy of the first Corridor is set to 4 or less, then the Daleks may use the set of Corridors \{ \{ 1,2 \}, \{ 2,3 \} \} (in particular, if it were set to less than 4, then this would be the only set of Corridors that they would use). However, if it is larger than 4, then they will instead use the set \{ \{2,3\}, \{3,1\} \}.
```python
def naiveSolve():
    
    
    
    return

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
    def find(self, a): #return parent of a. a and b are in same set if they have same parent
        acopy = a
        while a != self.parent[a]:
            a = self.parent[a]
        while acopy != a: #path compression
            self.parent[acopy], acopy = a, self.parent[acopy]
        return a
    def union(self, a, b): #union a and b
        self.parent[self.find(b)] = self.find(a)

def main():
    
    n,m=readIntArr()
    a=[]
    b=[]
    c=[]
    a1=b1=-1
    for _ in range(m):
        aa,bb,cc=readIntArr()
        if a1==-1: # exclude the 1st one first
            a1=aa; b1=bb
        else:
            a.append(aa); b.append(bb); c.append(cc)
    if n==2 or m+1==n:
        print(int(1e9))
        return
    
    idxes=list(range(m-1))
    idxes.sort(key=lambda i:c[i])
    
    uf=UnionFind(n+1)
    ans=int(1e9)
    for i in range(m-1):
        aa=a[idxes[i]]
        bb=b[idxes[i]]
        cc=c[idxes[i]]
        if uf.find(aa)!=uf.find(bb):
            uf.union(aa,bb)
        if uf.find(a1)==uf.find(b1):
            ans=cc
            break
    print(ans)
    
    return



import sys
input=sys.stdin.buffer.readline #FOR READING PURE INTEGER INPUTS (space separation ok)
# input=lambda: sys.stdin.readline().rstrip("\r\n") #FOR READING STRING/TEXT INPUTS.

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))
def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))
def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))
 
def readIntArr():
    return [int(x) for x in input().split()]
# def readFloatArr():
#     return [float(x) for x in input().split()]
 
def makeArr(defaultValFactory,dimensionArr): # eg. makeArr(lambda:0,[n,m])
    dv=defaultValFactory;da=dimensionArr
    if len(da)==1:return [dv() for _ in range(da[0])]
    else:return [makeArr(dv,da[1:]) for _ in range(da[0])]
 
def queryInteractive(r):
    print('? {}'.format(r))
    sys.stdout.flush()
    return readIntArr()
 
def answerInteractive(adj,n):
    print('!')
    for u in range(1,n+1):
        for v in adj[u]:
            if v>u:
                print('{} {}'.format(u,v))
    sys.stdout.flush()
 
inf=float('inf')
MOD=10**9+7
# MOD=998244353

from math import gcd,floor,ceil
# from math import floor,ceil # for Python2
 
for _abc in range(1):
    main()
```