George decided to prepare a Codesecrof round, so he has prepared *m* problems for the round. Let's number the problems with integers 1 through *m*. George estimates the *i*-th problem's complexity by integer *b*<sub class="lower-index">*i*</sub>.

To make the round good, he needs to put at least *n* problems there. Besides, he needs to have at least one problem with complexity exactly *a*<sub class="lower-index">1</sub>, at least one with complexity exactly *a*<sub class="lower-index">2</sub>, ..., and at least one with complexity exactly *a*<sub class="lower-index">*n*</sub>. Of course, the round can also have problems with other complexities.

George has a poor imagination. It's easier for him to make some already prepared problem simpler than to come up with a new one and prepare it. George is magnificent at simplifying problems. He can simplify any already prepared problem with complexity *c* to any positive integer complexity *d* (*c* ≥ *d*), by changing limits on the input data.

However, nothing is so simple. George understood that even if he simplifies some problems, he can run out of problems for a good round. That's why he decided to find out the minimum number of problems he needs to come up with in addition to the *m* he's prepared in order to make a good round. Note that George can come up with a new problem of any complexity.
The first line contains two integers *n* and *m* (1 ≤ *n*, *m* ≤ 3000) — the minimal number of problems in a good round and the number of problems George's prepared. The second line contains space-separated integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (1 ≤ *a*<sub class="lower-index">1</sub> &lt; *a*<sub class="lower-index">2</sub> &lt; ... &lt; *a*<sub class="lower-index">*n*</sub> ≤ 10<sup class="upper-index">6</sup>) — the requirements for the complexity of the problems in a good round. The third line contains space-separated integers *b*<sub class="lower-index">1</sub>, *b*<sub class="lower-index">2</sub>, ..., *b*<sub class="lower-index">*m*</sub> (1 ≤ *b*<sub class="lower-index">1</sub> ≤ *b*<sub class="lower-index">2</sub>... ≤ *b*<sub class="lower-index">*m*</sub> ≤ 10<sup class="upper-index">6</sup>) — the complexities of the problems prepared by George.
v, e = list(map(int, input().split(" ")))
edges = {}
for i in range(e-1):
    edges[i+1] = {}
for i in range(e):
    line = list(map(int, input().split(" ")))
    edges[line[0]][line[1]] = line[2]

def dijkstra(graph,src,dest,visited=[],distances={},predecessors={}):
    """ calculates a shortest path tree routed in src
    """    
    # a few sanity checks
    if src not in graph:
        raise TypeError('The root of the shortest path tree cannot be found')
    if dest not in graph:
        raise TypeError('The target of the shortest path cannot be found')    
    # ending condition
    if src == dest:
        # We build the shortest path and display it
        path=[]
        pred=dest
        while pred != None:
            path.append(pred)
            pred=predecessors.get(pred,None)
        path.reverse()
        estring = ""
        for i in path:
            estring += str(i) + " "
        print(estring) 
    else :     
        # if it is the initial  run, initializes the cost
        if not visited: 
            distances[src]=0
        # visit the neighbors
        for neighbor in graph[src] :
            if neighbor not in visited:
                new_distance = distances[src] + graph[src][neighbor]
                if new_distance < distances.get(neighbor,float('inf')):
                    distances[neighbor] = new_distance
                    predecessors[neighbor] = src
        # mark as visited
        visited.append(src)
        # now that all neighbors have been visited: recurse                         
        # select the non visited node with lowest distance 'x'
        # run Dijskstra with src='x'
        unvisited={}
        for k in graph:
            if k not in visited:
                unvisited[k] = distances.get(k,float('inf'))        
        x=min(unvisited, key=unvisited.get)
        dijkstra(graph,x,dest,visited,distances,predecessors)
        



'''
def dijkstra(graph, init, final, visited = [], distances = {}, ancestors = {}):
    if init == final:
        final_path = []
        path = final
        while path != None:
            final_path.append(path)
            path = ancestors[path][-1]
        print("huehuehue")
        return final_path
    else:
        if not visited:
            distances[init] = 0
        for neighbor in graph[init]:
            if neighbor not in visited:
                new_distance = distances[init] + graph[init][neighbor]
                if new_distance < distances[neighbor]:
                    distances[neighbor] = new_distance
                    ancestors[neighbor] = init
        visited.append(init)
        unvisited = {}
        for node in graph:
            if node not in visited:
                unvisited[node] = distences[node]
        next_node= sorted(unvisited.items(), key=operator.itemgetter(1))[0][0]
        dijkstra(graph, next_node, dest, visited, distances, ancestors)
    '''        
dijkstra(edges, 1, v)
